【算法】火车运煤问题

你是山西的一个煤老板，你在矿区开采了有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. 例解

#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