来转个和箱子有关的题目 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#1

发表于 2004-9-6 10:17 资料主页文集短消息看全部作者

看了楼下god_wolf的方法，又想出一种新方法：
公里油
050.00 50.5
050.51 50.0
100.51 25.5
101.53 25.0
103.65 24.0
153.65 12.5
155.83 12.0
205.83 06.5
210.37 06.0
260.37 03.5
270.37 03.0
303.71 02.0
503.71

晕原来车上装满了油，也就是相当于101桶，看来还能多走一些：
公里油
000.503 100
050.503 50.5
051.008 50.0
101.008 25.5
102.028 25.0
104.156 24.0
154.156 12.5
156.330 12.0
206.330 06.5
210.875 06.0
260.875 03.5
310.875 02.0
510.875

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#2

发表于 2004-9-6 15:51 资料主页文集短消息看全部作者

想了一下，6桶油走300公里应该是这样的，不知道对不对：
6桶走50公里，得3.5桶。然后卸下车上半桶，用一桶运一桶再走50公里，回程，再用半桶运一桶走50公里。此时已走100公里，还剩2桶。

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#3

发表于 2004-9-6 22:17 资料主页文集短消息看全部作者

选用若干中继点，可以把这道题拆为若干步骤，每一步开始时有(n+m)个桶，用n个桶送m个桶，其中n<[m]，([]为向下取整)。

先计算理论值，因为n<[m]，计算结果一定不多于50公里。
假设n和m均为0.5的整数倍，那么需要跑2[m]-1个单程，耗油共n桶，也就是用n桶能送m桶的距离为：100n/(2[m]-1)公里。

证明，该理论值一定能达到。
例1：
5桶油，用2桶送3桶，能送40公里，方法：
第一次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第二次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第三次，装0.4桶，载1桶，送出40公里，放下1桶。

例2：
5.5桶油，用2桶送3.5桶，能送40公里，方法：
第一次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第二次，装1桶，载1桶，送出40公里，放下1桶，返回，剩0.2桶。
第三次，装0.9桶，载1桶，送出40公里，放下1桶，剩0.5桶。

例3：
5桶油，用1.5桶送3.5桶，能送30公里，方法：
第一次，装1桶，载1桶，送出30公里，放下1桶，返回，剩0.4桶。
第二次，装1桶，载1桶，送出30公里，放下1桶，返回，剩0.4桶。
第三次，装0.8桶，载1桶，送出30公里，放下1桶，剩0.5桶。

建立函数f(x)和g(n,m)，f(x)为x桶油能走的距离，g(n,m)为n桶油送m桶油能走的距离。
那么函数f(x)的初始值
f(2)=200
递推关系
n= 0.5 to [x/2]
m= x - n
f(x) = max { g(n,m)+f(m) }
也就是在0.5到[x/2]中任意选择一个n，剩下的作为m，计算出n送m的距离再加上f(m)作为这个n值的最终距离。然后比较所有的n值的最终距离，取最大的一个最终距离为f(x)。
计算出f(x)之后，就可以再算f(x+0.5)直到f(100)。

代码略，以下是输出结果：
f(101.0)=511.83 49.5
f(51.5)=462.82  25.5
f(26.0)=412.82  12.5
f(13.5)=362.82  6.0
f( 7.5)=316.67  3.5
f( 4.0)=266.67  1.5
f( 2.5)=216.67  0.5
翻译一下：
公里油
000.00 101.
049.01 51.5
099.01 26.0
149.01 13.5
195.16 07.5
245.16 04.0
295.16 02.5
311.83 02.0
511.83

[广告] 真诚支持说岳，携手共创辉煌


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#4

发表于 2004-9-7 23:18 资料主页文集短消息看全部作者

QUOTE:

原帖由空度于2004-09-07, 22:10:18发表
149.01 13.5
195.16 07.5

周瑜的这步算法为什么不是

149.01 13.5
199.01 07.0

这是程序输出的结果，自动选择总路程最大值。
计算f(13.5)时，比较g(6,7.5)+f(7.5)和g(6.5,7)+f(7)以及其他一切分法的最大值。

g(6,7.5)=600/13=46.18
f(7.5)=316.67
g(6,7.5)+f(7.5)=362.82

g(6.5,7)=650/13=50
f(7)=309.52
g(6.5,7)+f(7)=359.52

明显前一个计算结果大的多。

[广告] 《精忠报国岳飞传完整版》火热发布