案例分析题
【说明】
0-1背包问题定义为:给定i个物品的价值v[1…i]、小重量w[1...i]和背包容量T，每个物品装到背包里或者不装到背包里。求最优的装包方案，使得所得到的价值最大。
0-1背包问题具有最优子结构性质。定义c[i][T]为最优装包方案所获得的最大价值，则可得到如下所示的递归式。
【c代码】
下面是算法的C语言实现。
(1)常量和变量说明
T: 背包容量
v[]:价值数组
w[]:重量数组
c[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值
(2) C程序
问答题
根据说明和C代码，填充C代码中的空(1) ~ (4)。
【正确答案】
（1）c[i][j]
不等于-1是已计算过该情况最大价值则直接返回c[i][j]。
（2）j>=w[i]
背包大于物品重量则考虑放入情况。
（3）Calculate_Max_Value(v,w,i-1,j-w[i]) + v[i]
求放入当前物品的最大价值。
（4）c[i][j]=temp
放入与不放入那种情况下价值大，那种情况就是当前最大价值。
【答案解析】
问答题
根据说明和C代码，算法采用了 (5) 设计策略。在求解过程中，采用了（6）(自底向上或者自顶向下)的方式。
【正确答案】
（5）动态规划
（6）自顶向下
【答案解析】
使用回归调用方式实现是自顶向下。
问答题
若5项物品的价值数组和重量数组分别为v[]= {0,1,6,18,22,28}和w[]= {0,1,2,5,6,7}背包容量为T= 11,则获得的最大价值为 (7)。
【正确答案】
（7）40
【答案解析】