对于背包问题，若令 x[k,h] 表示从前 k 项物品中取出并装入体积为 h 的背包的物品的最大价值，则当 k>0 且 h≥w_k 时，x[k,h]=?

(w_k 表示第 k 件物品的重量，c_k 表示第 k 件物品的价值）

在背包问题里，x[k,h]代表从前面k件物品中挑选，装入体积为h的背包时能获得的最大价值。当k>0且h≥wk（wk是第k件物品重量，ck是其价值 ）时，有两种决策思路。 1. 不放入第k件物品：此时背包能获得的最大价值，就是不考虑第k件物品，在前k – 1件物品中挑选，装入体积为h背包时的最大价值，即x[k – 1,h]。因为没有放入新物品，背包的价值和从前k – 1件物品中挑选装入体积h背包时是一样的。 2. 放入第k件物品：首先要保证背包有足够空间，即h≥wk 。放入第k件物品后，背包还剩h – wk的空间。那么此时背包的最大价值，就是在前k – 1件物品中挑选，装入体积为h – wk背包时的最大价值，再加上第k件物品的价值ck，也就是x[k – 1,h – wk] + ck。 要得到x[k,h]，就需要在这两种决策产生的价值中取较大值，所以x[k,h]=max(x[k – 1,h], x[k – 1,h – wk] + ck)。

01:40