骆驼和玉米 [No. 80]

一个骆驮运玉米从A地到B地, 骆驮一次最多运1000个玉米,A地距离B地有1000米远. 而骆驮每走1米就要吃一个玉米.现在有3000个玉米.现在要从A运到B.问到B地最多还能剩下多少个玉米?

wantalcs给出的答案是：

class Program
{
   private static readonly int _maxLoad = 1000;   //单次运载上限
    private static readonly int _totals = 3000;    //需要被运载总量
    private static readonly int _unitDeplete = 1;  //运输单位距离消耗食品量
    private static readonly int _road = 1000;      //全路长度
    /// <summary>
    /// 求本次实际运载量
    /// </summary>
    /// <param name="quantity">本次剩余需要运载的量</param>
    /// <returns>本次实际运载量</returns>
    private static int GetLoad(int quantity)
    {
        return Math.Min(quantity, _maxLoad);
    }
    /// <summary>
    /// 计算运载过程需要消耗的食品量
    /// </summary>
    /// <param name="x">运载距离</param>
    /// <returns>总消耗量</returns>
    private static int GetDepletion(int x)
    {
        return x * _unitDeplete;
    }
    /// <summary>
    /// 单段路程运载结果
    /// </summary>
    /// <param name="x">运载的路程</param>
    /// <param name="quantity">需要被运载的量</param>
    /// <returns>最后运到目的地的量</returns>
    private static int PartLoad(int x, int quantity)
    {
        int target = 0;         //运到目的地的量
        int origin = quantity;   //剩余需被运载量
        target = GetLoad(origin) - GetDepletion(x);
        origin = origin - GetLoad(origin);
        while (GetLoad(origin) > GetDepletion(2 * x))   //只要剩余可运量大于来回路程消耗量，就回头去运输
        {
            target += (GetLoad(origin) - GetDepletion(2 * x));
            origin -= (GetLoad(origin));
        }
        return target;
    }
    /// <summary>
    /// 计算是指定分段路程下，最终运到目的地的量
    /// </summary>
    /// <param name="x">分段路程长度</param>
    /// <returns>最终到达目的地量</returns>
    private static int FinalLoad(int x)
    {
        int road = _road;       //剩余路程
        int target = _totals;   //运到的量
        while (road > x)    //只要剩余路程大于单位路程，就继续运输
        {
            road -= x;
            target = PartLoad(x, target);
            if (target <= 0)    //如果把所有食品都消耗完了，运输失败，没意义继续下去了。
            {
                break;
            }
        }
        if (target > 0)
        {
            target = PartLoad(road, target);    //运输余下最后一段路程
        }
        return target > 0 ? target : 0;
    }
    static void Main(string[] args)
    {
        int unitRoad = 0;   //单位路程 
        int quantity = 0;   //最终运量
        for (int i = 1; i <= 1000; i++)
        {
            int target = FinalLoad(i);
            if (target > quantity)
            {
                quantity = target;
                unitRoad = i;
            }
        }
        Console.WriteLine(string.Format("当单位路程为{0}时，最后运载量最大，可达到{1}。", unitRoad, quantity));
        Console.ReadKey();
    }
}

这个问题明显应该使用动态规划算法。目前看来 wantalcs给出的算法是正确的，但我还不是特别的肯定。

本问题和解答来自：http://topic.csdn.net/u/20100710/08/3C83B4D1-974F-4038-8039-FC483D923177.html