完全背包问题与多重背包问题
完全背包问题的描述是“给定容积为\(V\)的背包与物品序列，物品\(i\)的价值与体积分别为\(A_i,B_i\)。设序列中每个物品有无限个可以取，如何取物品可使总价值最大”。《算法导论》中的钢条切割问题就是完全背包问题。
这个问题本身可以转化成(01)背包问题，虽然每种物品有无限个，但背包容量却是有限的，故对于物品\(i\)，其至多能被取\(\lfloor{V/B_i}\rfloor\)次(其中\(\lfloor \rfloor\)表示向下取整，即直接丢弃小数点后的数)，从无限变为有限后就很好处理了，只需要把这些一样的物体“平铺”开就能得到一个新的物品序列，然后用这个新的物品序列求解对应的(01)背包问题即可。
按上述思路可得状态转移方程\(F(k,V)=max\{~ F(i-1,V-mB_i) + mA_i ~|~ 0 \leq mB_i \leq V ~\}\)，这个方程可以理解成是从其“对应”的(01)背包的状态转移方程整理得到的，也可参照之前证明(01)背包的思路，来直接证明其正确性。在具体实现时，也要考虑好关于\(V-mB_i\)的边界情况，要根据每个“子问题”的\(k,V\)先确定\(m\)所能取到的最大个数。下面是一种求\(F\)的具体实现，也是利用二维数组来存储的。这里不再实现利用\(F\)得到具体解的程序。
1 2 3 4 5 6 7 8 9 10 11 12 13 | def dp(A, B, V): f = [[0 for j in range(V + 1)] for i in A] for i in range(len(A)): for j in range(V + 1): M = j // A[i] if i == 0: f[i][j] = M * B[i] else: f[i][j] = max([ (f[i - 1][j - m*A[i]] + m*B[i]) for m in range(M+1) ]) return f |
然后看多重背包问题，其描述为“给定容积为\(V\)的背包与物品序列，物品\(i\)的价值与体积分别为\(A_i,B_i\)。设第\(i\)个物品可取的总数是\(M_i\)，如何取物品使总价最大”。其和完全背包的区别在于前者的\(M_i\)是在题设显性给出的，后者是根据背包容积“隐式”给出的。状态转移方程为\(F(k,V)=max\{~ F(i-1,V-mB_i) + mA_i ~|~ 0 \leq m \leq M_i , ~ 0 \leq mB_i \leq V ~\}\)。