假设一次的最大功效数为w,剩下的包子数为x，前进的距离为y，那么
求w=x*y的最大值就是我们希望最优的

1.起点每次满载应该最优

在250公里处的状态为：剩下1750个包子...

/**
 * There are M breads at the starting point, the distance is N miles from the
 * beginning to the end. A person can carry C breads and will consume 1 per mile.
 * How many breads will be eventually carried over to the end?
 * 
 */

public class Moving
{
    private int m, n, c;
    
    public Moving(int M, int N, int C)
    {
        m = M; 
        n = N;
        c = C;
    }

    public int move()
    {
        int total = m;
        for (int i=0; i<n; i++)
        {
            System.out.println("moving 1 mile ..." + (i+1));
            total = move(total, 1);
            // This test is to show: (c-2*miles)*miles has a maximum
            // moving a distance up to this maximal point, this cost is the
            // same as moving 1 by 1 mile. 
            System.out.println("test this: " + (c-2*(i+1))*(i+1));
        }
        return total;
    }
    
    private int move(int totalBreads, int milesMoved)
    {
        System.out.println("total: " + totalBreads);
        if (totalBreads <= 0 || milesMoved < 0) return 0;
        // can't carry all of them once, so need to make a round trip.
        if (totalBreads > c) 
        {
            if (totalBreads - c > 2*milesMoved) // worth to come back
            {
                //System.out.println("going back ...");
                return c - 2 * milesMoved + move(totalBreads - c, milesMoved);
            }
            else // not worth to come back, so disgard the rest.
            {
                //System.out.println("not going back ...");
                return c - milesMoved;
            }
        }
        // can carry them once.
        else if (totalBreads <= milesMoved) return 0;
        else return totalBreads - milesMoved;
    }
    
    public static void main(String[] args)
    {
        Moving moving = new Moving(3000, 1000, 1000);
        System.out.println("total moved: " + moving.move());
    }
}

bwpc wrote:

程序中这个条件 if (totalBreads - c > milesMoved) // worth to come back
应该改成 if (totalBreads - c > 2*milesMoved),当然这并没有影响最后的结果（由于这个milesMoved取值为1）