第三节 背包问题   (1) (2) (3)
    有一个人背包上山，其可携带物品重量限度为a公斤。设有n种物品可供他选择装入背包中，已知第i种物品每件重为wi公斤，在上山过程中的作用是数量Xi的函数。问此人应如何选择携带物品（各几件），使所起作用最大。这就是著名的背包问题。类似的问题有运输中的货物装载数量、人造卫星内的物品装载问题等。
    
    
    这是一个整数规划问题。如果Xi只取0或1，又称0-1背包问题。 这类问题可以用动态规划方法求解。
    按可装入背包的物品的类别分阶段：k=1，2，…，n.
    状态变量表示允许装入的第k种物品至第n 种物品的总重量；
    决策变量表示装入的第k种物品的件数，则状态转移方程为：.
    设为装入第k种物品到第n种物品所对应的最大使用价值。则动态规划基本方程是：
    
    然后，由后至前逐步计算出 及相应的,最后算得 就是所求的最大价值，再按计算顺序反推回去，即可得到最优方案。