TwoDimensionBag 二维背包

问题

现有nn个珠宝(共nn种,每种11个),已知第ii个珠宝的价值是viv_{i},重量11w1iw1_{i},重量22w2iw2_{i}。给你一个背包,你可以自由挑选珠宝装到背包中,但背包可以装载的最大重量11weight1weight1,最大重量22weight2weight2。求背包能够装载珠宝的最大价值valuevalue

该问题与01背包的区别就是,重量属性变成了22维属性,背包中所有珠宝的总重量11不能超过weight1weight1,总重量22不能超过weight2weight2

解法

f(i,j,k)f(i,j,k)为背包中放入前ii件物品,重量11不大于jj,重量22不大于kk的最大价值,其中i[1,n]i \in [1,n]j[0,weight1]j \in [0,weight1]k[0,weight2]k \in [0,weight2]。有如下状态转移方程:

f(i,j,k)={0(intialize)i[0,n],j[0,weight1],k[0,weight2]maxf(i1,j,k),f(i1,jw1i,kw2i)+vi(loop)i[1,n],j[0,weight1],k[0,weight2],jw1i,kw2if(i,j,k) = \begin{cases} 0 & (intialize) & i \in [0,n], j \in [0,weight1], k \in [0,weight2] \\ max{f(i-1,j,k),f(i-1,j-w1_{i},k-w2_{i})+v_{i}} & (loop) & i \in [1,n], j \in[0,weight1], k \in [0,weight2], j \geq w1_{i}, k \geq w2_{i} \end{cases}

(1)(1) 初始化,背包中没有放入任何珠宝时f(i,j)=0f(i,j) = 0

(2)(2) 对于第ii个珠宝时,若装进背包,则背包的价值增大viv_{i},剩余重量11减小w1iw1_{i},剩余重量22减小w2iw2_{i},即f(i,j,k)=f(i1,jw1i,kw2i)+vif(i,j,k) = f(i-1,j-w1_{i},k-w2_{i})+v_{i}(其中jw1i,kw2ij \geq w1_{i}, k \geq w2_{i});若不装入背包,则一切维持不变,即f(i,j,k)=f(i1,j,k)f(i,j,k) = f(i-1,j,k)。选择这两种情形中的最大值;

f(n,weight1,weight2)f(n,weight1,weight2)即为nn个珠宝中重量11不超weight1weight1,重量22不超过weight2weight2的最大价值。该算法的时间复杂度是O(n×weight1×weight2)O(n \times weight1 \times weight2)

源码

TwoDimensionBag.h

TwoDimensionBag.cpp

测试

TwoDimensionBagTest.cpp

Last updated