【算法】火车运煤问题

你是山西的一个煤老板,你在矿区开采了有3000吨煤需要运送到市场上去卖,从你的矿区到市场有1000公里,你手里有一列烧煤的火车,这个火车最多只能装1000吨煤,且其能耗比较大——每一公里需要耗一吨煤。请问,作为一个懂编程的煤老板的你,你会怎么运送才能运最多的煤到集市?

1. 普通解

  1. 装1000吨煤,走250公里,扔下500吨煤,回矿山。
  2. 装1000吨煤,走到250公里处,拿起250吨煤继续向前到500公里处,扔下500吨煤,回矿山。此时火车上还有250吨,再加上在250公里处还有250吨煤,所以,火车是可以回矿山的。
  3. 装上最后1000吨煤,走到500公里处,装上那里的500吨煤,然后一直走到目的。

2. 最优解

从动态规划的角度求最优解:
假设起始运送货物量为t,重点路程为s,火车容量为c,可以运抵终点的最多货物量为函数 F(t, s)。
3种基本情况:
(1)t < s:货物量不足以运送到此距离,所以F(t, s) = 0;
(2)s < t < c:火车一次就可以装完货物,所以F(t, s) = t - s;
(3)2s < c 使得火车一次无法运完,但可以采用往返的方式多次运输,这种情况下最有的方式就是减少总共往返的次数,也就是直接运到终点而不在中间卸货,所以F(t, s) = (t / c - 1) * (c - 2s) - (c - s)

可得递归式:F(t, s) = max{ F( F(t, i), s - i)} (1 <= i < s)

3. 例解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include
using namespace std;
//总共3KT煤
#define TOTALCOAL 3000.0
//运送距离1000KM
#define DISTANCE 1000.0
//每次最多运送1000T
#define MAX_TRANS 1000.0
int main()
{
int n = TOTALCOAL / MAX_TRANS;
float anMidPoint[n];
float nTotalDis = 0;
for(int i = 0; i < (n – 1); i++)
{
anMidPoint[i] = MAX_TRANS / (2 * (n – i) – 1);
nTotalDis += anMidPoint[i];
}
anMidPoint[n – 1] = DISTANCE – nTotalDis;
cout << "Total coal: \t\t" << TOTALCOAL << " T" << endl;
cout << "Transport distance: \t" << DISTANCE << " KM" << endl;
cout << "Transport volume: \t" << MAX_TRANS << " T/KM"<< endl;
cout << "Profit: \t\t" << MAX_TRANS – anMidPoint[n – 1] << " T"<< endl;
return 0;
}
#: g++ CoalTrain.cpp
#: ./a.out
#: Total coal: 3000 T
#: Transport distance: 1000 KM
#: Transport volume: 1000 T/KM
#: Profit: 533.333 T
Yunjie Zhang wechat
扫一扫上面的二维码加我微信