l**********e
发帖数: 336 | |
x******a
发帖数: 6336 | 2 这个没戏，应该是相距1000迈，估计笔误
mile
【在 l**********e 的大作中提到】
: 是看以前版上的题目，觉得有些奇怪
|
l**********e
发帖数: 336 | 3 sorry, a typo,就是1000 mile
不过这样还是，一车最多带1000个苹果，等开到B，
不是全部没了吗？。。。
【在 x******a 的大作中提到】
: 这个没戏，应该是相距1000迈，估计笔误
:
: mile
|
r*******y
发帖数: 1081 | 4 感觉是2000个？
第一趟全掉地上了，后两趟每次掉一个捡一个？
mile
【在 l**********e 的大作中提到】
: 是看以前版上的题目，觉得有些奇怪
|
d*j
发帖数: 13780 | 5 感觉0个
第一趟全掉地上了，后两趟每次全掉地上了 ......... |
c********d
发帖数: 173 | 6 以前的链接是什么？
【在 l**********e 的大作中提到】
: sorry, a typo,就是1000 mile
: 不过这样还是，一车最多带1000个苹果，等开到B，
: 不是全部没了吗？。。。
|
c********d
发帖数: 173 | 7 以前的链接是什么？
【在 l**********e 的大作中提到】
: sorry, a typo,就是1000 mile
: 不过这样还是，一车最多带1000个苹果，等开到B，
: 不是全部没了吗？。。。
|
l**********e
发帖数: 336 | 8 这题觉得很奇怪，如果不允许把掉的捡起来，那么，车上苹果每mile掉一个，1000mile
之后肯定一个都没有了。。。不管运几趟，每次运几个，只要最大运载量不超过1000
如果允许捡起来这种行为，那么每mile掉一个，马上就捡起来，继续开，继续掉，继续
捡。。。如此下去，1000个肯定都能运过去，如果能开3趟，3000个都过去了
这样的题目有意思吗？
【在 r*******y 的大作中提到】
: 感觉是2000个？
: 第一趟全掉地上了，后两趟每次掉一个捡一个？
:
: mile
|
u******s
发帖数: 157 | 9 step 1：携带1000个苹果上车，开到1000/3处停下来，这时候有2000/3个苹果在车上。
把所有没有掉下去的苹果卸下来。如此往返三次，损失1000个苹果，运送2000个苹果到
1000/3处。
step 2：携带1000苹果上车，开500mile停下来，卸苹果。往返两次。再损失1000个苹
果，运送1000个苹果到500+1000/3处停下来。
step 3：装上最后的1000个苹果，开500/3mile到终点。最终运送2500/3个苹果。
key thought: how many apples you can carry and what's the number of
iterations that you can afford. Thus in the first step, 1000 apples while 3
iterations. In the second step, 1000 apples while 2 iterations. |
l**********e
发帖数: 336 | 10 谢谢～
那就是说苹果掉了不能用了，但是可以自己卸下来，然后下次再继续装，这个还算‘有
效’苹果，恩，那我再想想看
3
【在 u******s 的大作中提到】
: step 1：携带1000个苹果上车，开到1000/3处停下来，这时候有2000/3个苹果在车上。
: 把所有没有掉下去的苹果卸下来。如此往返三次，损失1000个苹果，运送2000个苹果到
: 1000/3处。
: step 2：携带1000苹果上车，开500mile停下来，卸苹果。往返两次。再损失1000个苹
: 果，运送1000个苹果到500+1000/3处停下来。
: step 3：装上最后的1000个苹果，开500/3mile到终点。最终运送2500/3个苹果。
: key thought: how many apples you can carry and what's the number of
: iterations that you can afford. Thus in the first step, 1000 apples while 3
: iterations. In the second step, 1000 apples while 2 iterations.
|
D**********d
发帖数: 849 | 11 厉害 !
3
【在 u******s 的大作中提到】
: step 1：携带1000个苹果上车，开到1000/3处停下来，这时候有2000/3个苹果在车上。
: 把所有没有掉下去的苹果卸下来。如此往返三次，损失1000个苹果，运送2000个苹果到
: 1000/3处。
: step 2：携带1000苹果上车，开500mile停下来，卸苹果。往返两次。再损失1000个苹
: 果，运送1000个苹果到500+1000/3处停下来。
: step 3：装上最后的1000个苹果，开500/3mile到终点。最终运送2500/3个苹果。
: key thought: how many apples you can carry and what's the number of
: iterations that you can afford. Thus in the first step, 1000 apples while 3
: iterations. In the second step, 1000 apples while 2 iterations.
|
l**********e
发帖数: 336 | 12 再赞一下你的解答～～
这个解答应该是能证明是最优解的
3
【在 u******s 的大作中提到】
: step 1：携带1000个苹果上车，开到1000/3处停下来，这时候有2000/3个苹果在车上。
: 把所有没有掉下去的苹果卸下来。如此往返三次，损失1000个苹果，运送2000个苹果到
: 1000/3处。
: step 2：携带1000苹果上车，开500mile停下来，卸苹果。往返两次。再损失1000个苹
: 果，运送1000个苹果到500+1000/3处停下来。
: step 3：装上最后的1000个苹果，开500/3mile到终点。最终运送2500/3个苹果。
: key thought: how many apples you can carry and what's the number of
: iterations that you can afford. Thus in the first step, 1000 apples while 3
: iterations. In the second step, 1000 apples while 2 iterations.
|
j********t
发帖数: 97 | 13 unichaos的思路很赞。按照这个思路可以进一步找到更优解, 3000/e.
首先，显然尽量满载可以降低损失率，所以每次都满载1000。
假设有N个苹果要从A点运到B点，AB之间距离占总里程的比例为x，也就是AB长1000x
mile。那么运送次数是N/1000. 损失率是(1000x) * (N/1000) / N = x.
如果把1000 mile 分成n段运输，记损失率为x1, x2, ... xn. 问题相当于让总的损失
率最低，从而转化成求最优化问题。
Max{ 3000 * (1-x1)(1-x2)...(1-xn) }
subject to x1 + x2 + ... + xn = 1
n=2, x1=x2=1/2, 3000 * 1/4
n=3, x1=x2=x3=1/3, 3000 * 8/27
...
n -> \infty, x_i = 1/n, \lim 3000 * (1-1/n)^n = 3000/e |
