室友参加某公司的笔试结束，问了我下面这道题：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
PS.中间任意地点可以丢下煤，也可以折返，折返过程中也需耗煤。
题目来源：CoolShell
变种题目包括：驴子运胡萝卜、马运草等。
乍一看，这题似乎有问题：1000吨带上去，开到终点就没了，怎么办？
转念一想，这题应该是可以选择在中途放下煤的。
在网上查看答案之前，自己模拟了一个比较典型的情况：
第一次运1000吨，在250km处放下500吨，返程；
第二次运1000吨，在500km处放下500吨，返程；
第三次运1000吨，到500km处刚好拿上500吨，直接走。
这样到终点就有了500吨。
感觉500这个答案既像是标答，又感觉不太准（要是随便一试就是答案这题也太水了吧）
另一个搞ACM的室友说，这是DP（Dinamic Programming，动态规划）问题。
看了一些分析之后，于是有了思路：
- 总共3000吨煤，一次出发最多只能运1000吨，那么最少要出发3次，且前两次返回起点时，火车为空；
- 最后一次出发不用返回；
- 既然前两次要返回，那么一定会在路上投放煤。不妨将起点计作A点，终点记作D点，路上的两点分别计作B、C点，其中B距起点A较近。
那么，目标就是求解最优的B、C点位置了。
整个运送过程如下：
而又可以将上述过程理解成：
即：先将煤运到中转站B，再运到中转站C，最后运到D。每次从一个中转站出发的时候一定尽量满载。
C到D一定是一次运完，所以C点存放1000吨。A到B至少3次运完，B点煤的数量比A少，比C多，只能是2000吨。
这样就可以求解了：
AB：走5次消耗1000吨，$AB=1000/5=200$.
BC：走3次消耗1000吨，$BC = 1000/3 = 333.3$
因此，从A到D最多运送533.3吨煤。
扩展：一般情况
原问题链接的评论区中，用户@albert分析的很好：
1000是基本刻度，解题精髓在于消耗多余的煤把煤移动到一个离终点更近的距离，最后一次运上1000吨然后从这个地方直达终点，还能剩下的就是你能运达的煤。 煤越多需要的搬运次数越多，搬运次数越多消耗就越多。 要运送到相对较近的距离对煤的消耗量为$(2n + 1)Step$,Step为一次行进的步长,$n=totalNum / 1000-1$，totalNum为总煤量 根据这个公式， 当煤量为2000～3000时，你的运送成本是5Step 1000～2000时为3Step， 小于等于1000时为1Step, 所以第一次选择行进200公里，消耗的煤为5 × 200 = 1000，剩余2000（2000～3000） 第二次选择行进333公里，消耗的煤为3 × 333 = 999 =～ 1000，剩余1000（1000～2000） 此时一共行进了533公里，还剩下1000吨煤，最后到达终点还剩533吨（1000内）
其实次数是无所谓的，关键是把握消耗的数量级。比如第二个刻度分解了 第一次选择行进200公里，消耗的煤为5 × 200 = 1000，剩余2000（2000～3000） 第二次选择行进200公里，消耗的煤为3 × 200 = 600，剩余1400（1000～2000） 第三次选择行进100公里，消耗的煤为3 × 100 = 300， 剩余1100（1000～2000） 第四次选择行进33公里，消耗3×33=99～=100，剩余1000（1000～2000） 此时一共行进了533公里，还剩下1000吨煤，最后到达终点还剩533吨（1000内）
以及，本题目其实具备初中数学知识（甚至小学知识）就已经够解了，很多时候善于思考还是很重要的。
（可惜我在拿到答案前并没有思考出来…干脆记一笔方便以后回味吧）