二、 问题分析
1. 初步部分
(1) 证明该问题满足最优子结构
证明:设有 x1,x2,…,xn 共 n 个物品,他们的重量为 w1,w2,…,
wn,他们的价值为 v1,v2,…,vn。背包可容纳最大重量为 C。
设(y1,y2,…,yk-1)是 x1~xn 的一个最优解,我们可以推断:
① 如果 yk=1,那么 m[k-1][MaxWeight-wk]+vk>m[k-1][MaxWeight]。
我们假设 m[k-1][MaxWeight-wk]+vk<=m[k-1][MaxWeight],那么就有
m[k][MaxWeight]= m[k-1][MaxWeight-wk]+vk<=m[k-1][MaxWeight],
就有(y1,y2,…,yk-1)不是最优解,与前提矛盾。
② 如果 yk=0,那么 m[k-1][MaxWeight-wk]+vk<=m[k-1][MaxWeight]。
证明同上。
(2) 给出递推式子
(3) 基于动态规划实现算法
我们可以采用一个二维数组去解决:m[i][j],其中 i 代表加入背包的
是前 i 件物品,j 表示背包的承重,m[i][j]表示当前状态下能放进背
包里面的物品的最大总价值。那么,m[n][m]就是我们的最终结果了。
采用动态规划,必须要知道初始状态和状态转移方程。初始状态很容
易就能知道,那么状态转移方程如何求呢?对于一件物品,我们有放
进或者不放进背包两种选择:
① 假如我们放进背包,m[i][j] = m[i - 1][j - weight[i]] +
value[i],这里的 m[i - 1][j - weight[i]] + value[i]应该这么理
解:在没放这件物品之前的状态值加上要放进去这件物品的价值。而
对于 m[i - 1][j - weight[i]]这部分,i - 1 很容易理解,关键是 j
- weight[i]这里,我们要明白:要把这件物品放进背包,就得在背包
里面预留这一部分空间。
② 假如我们不放进背包,m[i][j] = m[i - 1][j],这个很容易理解。
因此,我们的状态转移方程就是:m[i][j] = max(m[i][j] = m[i -
1][j] , m[i - 1][j - weight[i]] + value[i])
③ 当然,还有一种特殊的情况,就是背包放不下当前这一件物品,这种
情况下 m[i][j] = m[i - 1][j]。
(4) 分析算法的复杂度
从 m[i,j]的递归式容易看出,算法需要 O(nC)计算时间。当背包容量 C
很大时,算法需要的计算时间较多。例如,当 C>2^n 时,算法需要
Ω(n2^n)计算时间。
2. 选做部分
(1) 上述算法要求所给物品的重量必须是整数,而实际处理问题时无法避
免物品的重量是小数的情况,试编写一个能够处理重量为小数的情
况。