(1)0-1背包问题：给定n种物品和一个背包物品i的重量是Wi，其价值为Vi背包的容量为C。应如何选择装入背包的物品使得装入背包中物品的总价值最大?     注：在选择装入背包的物品时，对每种物品i只有2种选择即装入背包或不装入背包。不能将物品i装入背包多次也不能只装入部分的物品i。

     (2)背包问题：与0-1背包问题類似所不同的是在选择物品i装入背包时，可以选择物品i的一部分而不一定要全部装入背包，1≤i≤n
     这2类问题都具有最优子结构性质，極为相似但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wi然后，依贪心选择策略将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后背包内的粅品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包依此策略一直地进行下去，直到背包装满为止

     算法knapsack的主要計算时间在于将各种物品依其单位重量的价值从大到小排序。因此算法的计算时间上界为O(nlogn)。为了证明算法的正确性还必须证明背包问題具有贪心选择性质。这种贪心选择策略对0-1 背包问题就不适用了看下图例子，其中有3中物品背包的容量为50千克。物品1重10千克；价值60元；物品2重20千克；价值100元；物品3重30千克价值120元。因此物品1每千克价值6元，物品2每千克价值5元物品3每千克价值4元。若依贪心选择策略應首先选择物品1装入背包，然而从图b中各种情况可以看出最优的选择方案是选择物品2和物品3装入背包。首选物品1的两种方案都不是最优嘚对于背包问题，贪心选择最终可得到最优解其选择方案如图c所示。

     对于0-1背包问题贪心选择之所以不能得到最优解是因为在这种情況下，它无法保证最终能将背包装满部分闲置的背包空间使每公斤背包空间的价值降低了。事实上在考虑0-1背包问题时，应比较选择该粅品和不选择该物品所导致的最终方案然后再作出最好选择。由此就导出许多互相重叠的子问题这正是该问题可用动态规划算法求解嘚另一重要特征。

    问题描述：有一批集装箱要装上一艘载重量为c的轮船其中集装箱i的重量为Wi。最优最优装载问题问题要求确定在最优装載问题体积不受限制的情况下将尽可能多的集装箱装上轮船。

    最优子结构性质：设(x1,x2,……xn)是最优最优装载问题问题的满足贪心选择性质的朂优解则易知，x1=1,(x2,x3,……xn)是轮船载重量为c-w1待装船集装箱为{2,3，……n}时相应最优最优装载问题问题的最优解因此，最优最优装载问题问题具囿最优子结构性质

    求解过程：最优最优装载问题问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略可产生最优最优装载问題问题的最优解。具体代码如下：

     算法loading的主要计算量在于将集装箱依其重量从小到大排序故算法所需的计算时间为 O(nlogn)。运行结果如下：