首页 > 代码库 > Java学习笔记——山西煤老板蛋疼的拉车问题

Java学习笔记——山西煤老板蛋疼的拉车问题

 

小荷才露尖尖角,早有蜻蜓立上头

              ——小池

这个问题是这样描述的:

山西煤老板有3000吨煤,要运到1000km公里外的地方卖。他选择使用火车来运煤,每辆火车行驶一公里将消耗一吨煤,且火车载货上限为1000吨。

山西煤老板是个懂代码的家伙,你觉得它最多能拉多少煤过去?

且不论懂代码的人为什么要选择这么蛋疼的方式拉煤。。算了,直接把它抽象成数学问题。

山西煤老板的煤总量为amount,总里程为totalTrail,火车载重为load

这类问题存在隐藏条件:

1、假设每辆车都能装满货物,那么amount一定是load的整数倍。(因为这样可以最大化送达货物)

2、载物工具一定是每走一步消耗一个物品。(因为系数为1最简单,但是其实这个系数是灵活的,而且并不麻烦。)

这道题举的例子比较简单,心算也是无压力的,主要讲讲思路。

3000t煤先用3辆车拉满,行至1000/3(km)处,三辆车一共损失了负载1000t煤,停车,把剩下的2000t煤装到2辆车里拉,再往前行驶1000/2(km),又损失了1000t煤。最后1车拉走这1000t煤。

∴amount = 1000-1000(1-1/2-1/3)=833.3t煤

代码用递归来实现,解出两个出口:

1、递归...最后一趟车了,拉完,结束

2、递归...最后几辆车了,拉完,结束

 1 package cn.train;
 2 
 3 public class Train {
 4     public static void main(String[] args) {
 5         int huoWu = 3000;
 6         int load = 1000;
 7         double totaltrail = 1000;
 8         huoWu = calculate(huoWu, load, 0.0, totaltrail);
 9         System.out.println("剩余货物为" + huoWu);
10     }
11     public static int calculate (int huoWu,int load,double trail,double totaltrail){
12         int quantity = huoWu/load;//计算车数
13         //不到最后一车就拉完了
14         if (totaltrail-trail < load/quantity) {
15             huoWu -= quantity*(totaltrail-trail);
16             return huoWu;
17         }
18         //最后一车了
19         if (huoWu == load) {
20             huoWu -= (int)(totaltrail - trail);
21             return huoWu;
22         }
23         trail += load/quantity;//开始走了
24         huoWu -= load;
25         return calculate(huoWu, load, trail, totaltrail);
26     }
27 }

 

Java学习笔记——山西煤老板蛋疼的拉车问题