51-算法设计

4.9.2　算法设计

有n个物品，每个物品的重量为w[i]，价值为v[i]，购物车的容量为W。选若干个物品放入购物车，在不超过容量的前提下使获得的价值最大。

（1）确定合适的数据结构

采用一维数组w[i]、v[i]来记录第i个物品的重量和价值；二维数组用c[i][j]表示前i件物品放入一个容量为j的购物车可以获得的最大价值。

（2）初始化

初始化c[][]数组0行0列为0：c[0][j]=0，c[i][0] =0，其中i=0，1，2，…，n，j=0，1，2，…，W。

（3）循环阶段

• 按照递归式计算第1个物品的处理情况，得到c[1][j]，j=1，2，…，W。
• 按照递归式计算第2个物品的处理情况，得到c[2][j]，j=1，2，…，W。
• 以此类推，按照递归式计算第n个物品的处理情况，得到c[n][j]，j=1，2，…，W。

（4）构造最优解

c[n][W]就是不超过购物车容量能放入物品的最大价值。如果还想知道具体放入了哪些物品，就需要根据c[][]数组逆向构造最优解。我们可以用一维数组x[i]来存储解向量。

• 首先i=n，j=W，如果c[i][j]>c[i−1][j]，则说明第n个物品放入了购物车，令x[n]=1，j−=w[n]；如果c[i][j]c[i−1][j]，则说明第n个物品没有放入购物车，令x[n]=0。
• i−−，继续查找答案。
• 直到i=1处理完毕。

这时已经得到了解向量（x[1]，x[2]，…，x[n]），可以直接输出该解向量，也可以仅把x[i]=1的货物序号i输出。