问题
现有n个珠宝(共n种,每种1个),已知第i个珠宝的价值是vi,重量1是w1i,重量2是w2i。给你一个背包,你可以自由挑选珠宝装到背包中,但背包可以装载的最大重量1为weight1,最大重量2为weight2。求背包能够装载珠宝的最大价值value。
该问题与01背包的区别就是,重量属性变成了2维属性,背包中所有珠宝的总重量1不能超过weight1,总重量2不能超过weight2。
解法
设f(i,j,k)为背包中放入前i件物品,重量1不大于j,重量2不大于k的最大价值,其中i∈[1,n],j∈[0,weight1],k∈[0,weight2]。有如下状态转移方程:
f(i,j,k)={0maxf(i−1,j,k),f(i−1,j−w1i,k−w2i)+vi(intialize)(loop)i∈[0,n],j∈[0,weight1],k∈[0,weight2]i∈[1,n],j∈[0,weight1],k∈[0,weight2],j≥w1i,k≥w2i (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)。
源码
TwoDimensionBag.h
TwoDimensionBag.cpp
测试
TwoDimensionBagTest.cpp