设f(i,j,k)为背包中放入前i件物品,重量1不大于j,重量2不大于k的最大价值,其中i∈[1,n],j∈[0,weight1],k∈[0,weight2]。有如下状态转移方程:
(1) 初始化,背包中没有放入任何珠宝时f(i,j)=0;
(2) 对于第i个珠宝时,若装进背包,则背包的价值增大vi,剩余重量1减小w1i,剩余重量2减小w2i,即f(i,j,k)=f(i−1,j−w1i,k−w2i)+vi(其中j≥w1i,k≥w2i);若不装入背包,则一切维持不变,即f(i,j,k)=f(i−1,j,k)。选择这两种情形中的最大值;
f(n,weight1,weight2)即为n个珠宝中重量1不超weight1,重量2不超过weight2的最大价值。该算法的时间复杂度是O(n×weight1×weight2)。