背包问题总结【01,恰好/不超过,完全,多重,路径记录,应用】

有N件物品和一个容量为V的背包。第i件物品的体积是w[i],价值是v[i]。

1.0-1 背包

求解将哪些物品装入背包可使价值总和最大,每种物品至多只能选择一件

dp[i][j]表示第i件物品放入容量为j的背包所得的最大价值

dp[i][j]=max{dp[i-1][j-w[i]]+v[i] , dp[i-1][j]};

这里我们从j=V倒推回来的话可以优化成

dp[j]=max{dp[j] , dp[j-w[i]]+v[i]};

核心代码:

for(i=0;i<=V;i++){
dp[i] = 0;//初始化均为0
}
for(i=1;i<=n;i++){
for(j=V;j>=w[i];j--){//倒序更新,对于重量w[i]小于j的不作更新
//choice[i][j] = true;//如需记录,则可另创一个辅助数组(详见下文)
dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
}
}

dp[V]即为最大的价值


2.恰好装满时

此时只需改变初始值,即

#define INF 0x7fffffff
for(i=1;i<=V;i++){
dp[i] = INF;//除dp[0]外,其余均初始化为无穷
}
dp[0] = 0;

同时在状态转移前需加判断,if (dp[j - w[i]] != INF) dp=……

可以这样理解:初始化的dp 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可以在什么也不装的状态下被 “恰好装满” ,此时背包价值为0。其他容量的背包均没有合法的解,属于未定义的状态,所以都应该被赋值为 −∞ 。当前的合法解,一定是从之前的合法状态推得的

如果背包并非必须被装满,那么任何容量的背包都有一个合法解 “什么也不装”,这个解的价值为0,所以初始化时状态的值也就全部为0了。


3.完全背包问题

有N种物品和一个容量为V的背包,每种物品都有无限件。每件费用是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这时候对于每件物品就不是放与不放的问题了,而是放0件、1件…….

dp[i][j]表示容量为j的背包第i件物品是否要再一次放入所以我们要从0-V顺序循环

dp[i][j]=max{dp[i][j-w[i]]+v[i],dp[i-1][j]}(注意这里和01背包的区别,第i件物品可以多次放)

优化后:dp[j]=max{dp[j] , dp[j-w[i]]+v[i]};

核心代码:

for(i=1;i<=n;i++){
for(j=w[i];j<=V;j++){//注意到与一般背包相比,改变的只是遍历的顺序
dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
}
}

dp[V]即为最大的价值


4.多重背包问题

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。

拆分:多重背包问题限定了一种物品的个数,解决多重背包问题,只需要把它转化为0-1背包问题即可。比如,有2件价值为5,重量为2的同一物品,我们就可以分为物品a和物品b,a和b的价值都为5,重量都为2,但我们把它们视作不同的物品。

核心代码:

int k = n + 1;
for (int i = 1; i <= n; i++) {//拆分
while (num[i] != 1) {
weight[k] = weight[i];
value[k] = value[i];
k++;
num[i]--;
}
}

若对时间复杂度要求较高,则可采用以下的分解方法

int c = 1;
while(k-c>0){//对物品的数量k,拆分成1,2,4,8……
k-=c;
list[++ cnt].w = c * w;
list[cnt].v = c * v; //拆分后的物品重量和价格均为组成改物品的质量与价格总和
c *= 2;
}
list[++ cnt].w = w * k;
list[cnt].v = v * k;

//接着对拆分后的所有物品进行0-1背包处理即可

附:记录所选路径

新增二维数组choice[i][j],表示第i件物品是否已放入容量为j的背包

for(i=0;i<=V;i++){
dp[i] = 0;//初始化均为0
}
for(i=1;i<=n;i++){
for(j=V;j>=w[i];j--){
choice[i][j] = true;//记录所选结果
dp[j]=max{dp[j],dp[j-w[i]]+v[i]};
}
}

//输出
vector<int> arr;
int v = m, index = n;
while(v > 0) {
if(choice[index][v] == true) {//若第index个物品已放入
arr.push_back(w[index]);
v -= w[index];//体积减去相应的值
}
index--;//在index-1个物品中继续寻找(从后往前)
}
for(int i = 0; i < arr.size(); i++) {
if(i != 0) printf(" ");
printf("%d", arr[i]);
}

背包问题小结

1.一维的0-1背包为什么逆序而完全背包为什么顺序?

保证更新f[j]时,f[ j - weight[i] ]是没有放入物品i时的数据,即f[ i - 1 ][ j - weight[i] ],因为0-1背包每个物品至多被选一次。而完全背包中,每个物品可以被选无限次,那么状态f[i][j]正好可以由可能已经放入物品i的状态f[ i - 1 ][ j - weight[i] ]转移而来。所以,遍历顺序改为顺序时,就是完全背包问题,其余都不用变

2.完全背包 和 01背包 的区别仅在于状态更新时的遍历顺序。 01背包是逆序,完全背包是顺序

3.不超过容量恰好装满 的区别仅在于二者的初始化

前者全0,后者一维:除dp[0]为0外,其余dp[j]都是负无穷;二维:dp[i][0] = 0(第一列),其余全为0x80000000

4.0-1背包循环边界 i:[1,N],j:[V,weight[i]]


更多背包问题

以下问题均可转化为背包问题进行求解(持续更新):

https://www.liuchuo.net/archives/2323

Leetcode: 322,416,474,518,1049





改编自:

https://blog.csdn.net/sun897949163/article/details/49559679

https://blog.csdn.net/dr_unknown/article/details/51275471

《王道计算机考研机试指南》

Author: Apiao
Link: http://zc-apiao.space/2018/08/17/2018-08-17/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.