e*****e
发帖数: 3 | 1 题目如下，在coolshell上看到
http://coolshell.cn/articles/4429.html
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿
区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其
能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎
么运送才能运最多的煤到集市？
Leetcode 上有一道类似的题
http://leetcode.com/2011/01/nuts-in-oasis-interview-question-fr
这题如何用dp解？我一开始想用一个m[1000,3000]的数组，保存d距离运n吨煤最多剩下
的煤。后来发现不对，因为没考虑火车最后要停在终点一边。 |
f*******t
发帖数: 7549 | 2 不科学啊，耗煤的速度应该跟当前火车上煤的重量成正比，而不是固定的值 |
z***2
发帖数: 66 | 3 really? dp can work on this problem?
the train need to go back and forth....@@ |
z*******g
发帖数: 18 | 4 我的方法是
首先：分三次把煤运到离起始地200公里的地方A。前两次每次卸掉600吨的煤回去，
最后一次到A的时候一共有煤2000吨。200是从方程 1000-2x+1000-2x+1000-x = 2000
得到的。
现在这个问题就转变为另外一个问题，一共有2000吨煤，怎么运最多的煤到800公里以
外的地方。同样的思路，先运到一个地方卸煤，然后再装煤，要求是最后剩的煤只有
1000吨，这样才可以最后一次运到目的地。这个地点可以解下面这个方程
1000-2x + 1000 - x = 1000, x = 1000/3。
最后我们的问题变为，有1000吨的煤，离目的地1000-200-1000/3 = 1400/3 公里，怎
么运最多的煤。这个简单，一车直接把所有的煤拖过去，这样到达目的地就会有
1000-1400/3 = 1600/3吨的煤。 |
c********t
发帖数: 5706 | 5 对的。我是这么推得。
1 假设我们要把3000吨先运到一个中间点 x0, 因为3000吨要分3次运，第一二次都要往
返，第三次单程，所以这段距离要走5次。
2.如果发现当只剩下2000吨以下时，就只需要分两次运了，剩下的距离最多只用走3次
。所以要求x0尽量小，即只用1000吨，1000/5=200
3。同理可推第二个距离为 1000/3=333
4，剩下1000吨跑 467距离，剩余533吨
【在 z*******g 的大作中提到】
: 我的方法是
: 首先：分三次把煤运到离起始地200公里的地方A。前两次每次卸掉600吨的煤回去，
: 最后一次到A的时候一共有煤2000吨。200是从方程 1000-2x+1000-2x+1000-x = 2000
: 得到的。
: 现在这个问题就转变为另外一个问题，一共有2000吨煤，怎么运最多的煤到800公里以
: 外的地方。同样的思路，先运到一个地方卸煤，然后再装煤，要求是最后剩的煤只有
: 1000吨，这样才可以最后一次运到目的地。这个地点可以解下面这个方程
: 1000-2x + 1000 - x = 1000, x = 1000/3。
: 最后我们的问题变为，有1000吨的煤，离目的地1000-200-1000/3 = 1400/3 公里，怎
: 么运最多的煤。这个简单，一车直接把所有的煤拖过去，这样到达目的地就会有
|
z***2
发帖数: 66 | 6 佩服！
import java.util.*;
class train {
public static void main(String[] args) {
double table[]=new double [10001];
table[0]=3000.0;
for(int i =1; i
double localMax=-1.0;
double curDistance= i/10+ (double)(i%10)*1/10;
//System.out.println(curDistance);
for(int j=0; j
double totalLeft = table[j];
double prevDistance= j/10+ (double)(j%10)*1/10;
double distance= curDistance-prevDistance;
if(totalLeft>=2000){
double result=totalLeft- 5*distance;
localMax=Math.max(localMax,result);
}
else if(totalLeft>=1000){
double result=totalLeft- 3*distance;
localMax=Math.max(localMax,result);
}
else{
double result=totalLeft- distance;
localMax=Math.max(localMax,result);
}
}
table[i]=localMax;
}
System.out.println(table[10000]);
}
} |
G****A
发帖数: 4160 | 7 这个方法有个隐含assumption: "所有货物先运到同一个(非终点)地点"。虽然我也认为
运到不同地点不会lead to更好结果。但是需要证明.
【在 z*******g 的大作中提到】
: 我的方法是
: 首先：分三次把煤运到离起始地200公里的地方A。前两次每次卸掉600吨的煤回去，
: 最后一次到A的时候一共有煤2000吨。200是从方程 1000-2x+1000-2x+1000-x = 2000
: 得到的。
: 现在这个问题就转变为另外一个问题，一共有2000吨煤，怎么运最多的煤到800公里以
: 外的地方。同样的思路，先运到一个地方卸煤，然后再装煤，要求是最后剩的煤只有
: 1000吨，这样才可以最后一次运到目的地。这个地点可以解下面这个方程
: 1000-2x + 1000 - x = 1000, x = 1000/3。
: 最后我们的问题变为，有1000吨的煤，离目的地1000-200-1000/3 = 1400/3 公里，怎
: 么运最多的煤。这个简单，一车直接把所有的煤拖过去，这样到达目的地就会有
|
z***2
发帖数: 66 | 8 同問一下， 飞机加油问题 可以DP 解決嗎？
已知
每个飞机只有一个油箱
飞机之间可以相互加油(注意是相互，没有加油机)
一箱油可供一架飞机绕地球飞半圈
所有飞机从同一机场起飞，而且必须都安全返回机场，不允许中途降落，中间没有飞机场
问题：
为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架次飞机? |
