背包问题大汇总
文章目录
01背包
问题：
有Ｎ件物品和一个容量为Ｖ的背包，第ｉ件物品的费用（体积）是ｗ［ｉ］，价值是ｃ［ｉ],求解将哪些物品装入背包可使这些物品的费用综合不超过背包容量，且价值总和最大
思路：
f[i][v]表示前i件物品（部分或全部）恰放入一个容量为v的背包可以获得的最大价值。
转移方程：
（f的初始值为负无穷）
f [ i ][ v ] = m a x ( f [i - 1 ] [ v ] , f [i - 1 ] [ v -w [ i ] ] + c [ i ] )
这是最基础的背包dp，我们在考虑dp问题的时候，这么想，f[i][v]的状态是怎么来的？也就是第i件物品选择方式？有两种方式，第一种就是第i件商品不拿，那么f[i][v]的状态就是前i-1件物品恰放入一个容量为v的背包（即f[i-1][v]）直接转移过来的，另外一种就是第i件商品选择拿，那么f[i][v]的状态就是前i-1件物品恰放入一个容量为v-w[i]的背包（即f[i-1][v-w[i]]）再加入第i件商品（c[i]），其实就是末状态（f[i][v]）将第i件商品去除，可以得到初状态（f[i-1][v-w[i]]）
本质就是由已知推未知
这样最后答案是max(f[N][0…V])，因为我们在定义状态f时说的“恰”，也就是最佳情况并不一定是背包要装满，所以要取各种状态的最大值。
怎么样这个“恰”去掉呢？我们可以将所有f[i][j]初始化为0，也就是最开始的f[i][j]是有意义的，只是价值为0，可以看做无物品的背包价值都是0，这样最后的结果就是f[N][V]
小结：初始化为0------>不超过容量V
初始化为负无穷-------->恰好为容量V
空间优化复杂度
我们可以用一维的f[i]来代替上面的二维数组
for i=1…N
for v=V…0
f [v ] = max ( f[ v ] , f[ v- w [ i ] ] + c [ i ] )
我们在每次主循环时用v=V…0的逆序推f[v]，这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1][v-w[i]]的值。
代码
二维：
//f[i][v]表示前i件物品，总质量不超过v的最优价值
for(int i=1;i<=N;i++)
{
for(int v=V;v>0;v--)
{
if(w[i]<=v)f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);//如果能装下
else f[i][v]=f[i-1][v];
}
}
printf("%d",f[N][V]);
一维：
//f[v]表示质量不超过v公斤的最大价值
for(int i=1;i<=N;i++)
{
for(int v=V;v>=w[i];v--)//避免数组出现负下标
{
f[v]=max(f[v],f[v-w[i]]+c[i]);
}
}
printf("%d",f[V]);
完全背包
问题：
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是w[i],价值是c[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
思路：
和01背包的区别在于，每件物品不再只有取和不取两种状态，而是有取0件，取1件，取2件…很多种。
我们用01背包的方式来做,f[i][v]表示前i种物品恰好放入一个质量为v的背包的最大权值
f [ i ] [ v ] = m a x (f [ i - 1 ] [ v - k * w [i ] ] + k * c [ i ] | 0 < =k * w [ i ] <= v )
使用一维方程：
for i=1…N
for v=0…V
f [v ] = m a x (f [ v ] , f[ v - w [i ] ] +c [ i ] )、
你会发现与01背包相比，仅仅是把v的枚举顺序倒了过来
为啥呢？
01背包中v是从V->0，这是因为为了保证第i次循环中的状态f[i][v]是由上一个状态f[i-1][v-w[i]]递推而来，这样可以确定每个物品只选一次，我们在考虑“加选第i件物品”这一策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-w[i]]
而完全背包中物品的数量是无限的，所以在考虑“加选第i件物品”时，需要的是一个已经选入第i种物品的子结果f[i][v-w[i]]，也就是再已放入第i种物品的基础上再进行转移，所以要采用v=0->V的顺序
二维方程的话：
f [ i ] [ v ] = max ( f [ i - 1 ] [ v ] , f[ i ] [ v - w [ i ] ]+ c [ i ] )
代码：
f[i][v]表示前i件物品，总质量不超过v的最优价值
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
if(v<w[i])f[i][v]=f[i-1][v];
else
{
f[i][v]=max(f[i-1][v],f[i][v-w[i]]+c[i]);
}
}
}
printf("%d",f[N][V]);
f[v]表示质量不超过v公斤的最大价值
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
if(v>w[i])f[v]=max(f[v-w[i]]+c[i],f[v]);
}
}
printf("%d",f[V]);
优化
完全背包中，如果两个物品i与j，w[i]<=w[j]&&c[i]>=c[j],物品j就可以去掉，也就是一个物品占空间又大，价值还低，那要他干啥，j完全可以被i代替。这是一个简单的小优化
我们还可以把完全背包问题转化成01背包问题来解
因为背包容量是给定的，所以就可以算出每件物品最多可以装多少，将无限数量转变成有限数量，用01背包去做
但是这样的转变也太low了，对程序优化不了多少，更高效的转化是：把第i种物品拆成费用为w[i]*2k,价值拆成c[i]*wk的若干件物品，k满足w[i]*2k<V。二进制拆分的原理我们可以用 1,2,4,8…2n 表示出1 到 2n+1−1的所有数.利用二进制的思想来优化问题，不管最优策略是选几件第i种商品，总可以写成若干个2k件物品的和。把每件物品拆成O(log(V/w[i])+1)件物品
多重背包
问题：
有N种物品和一个容量为V的背包，第i种物品最多有n[i]件可用，每件费用是w[i],价值是c[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
思路：
和完全背包很相似，区别在于每个物品的数量是明确的是固定的，那直接就可以把完全背包的式子拿过来
f [ i ] [ v ] = m a x (f [ i - 1 ] [ v - k * w [i ] ] + k * c [ i ] | 0 < =k * <= n[i] )
一维的就是 f [ v] = max ( f[ v ] , f [ v - k * w [ i] ] + k* c [ i ] );
区别是k的范围是0~n[i]
但是光能这么做怎么够，我们看看怎么转化成最基础的01背包
最简单粗暴的就是你吧第i件物品换成n[i]件01背包中物品，就是把一种多件看作是多种一件，但是这样复杂度不变O(Vsum(n[i]))，意义不大，怎么才能降低负责度
完全背包我们讲了二进制的方式来优化，这里我们也考虑二进制的思想。把第i种物品换成若干件物品，每个物品有一个系数，这件物品的费用和价值等于原本物品的乘以系数，而这些系数分别是2的k次方（系数为0,2，4,），最后一个系数是n[i]-2k+1(剩下的)。例如13就可以拆分成系数为1,2，4,6（因为8达不到，所以用13减去前面的1，2，4，得到6）的四件物品
这样就将第i种物品分成O（logn[i]）种物品，将原问题转化为了复杂度为O（Vsum(logn[i])的01背包问题
代码：
朴素算法：
for(int i=1;i<=n;i++)
{
for(int j=V;j>=0;j--)
{
for(int k=0;k<=n[i];k++)
{
if(j-k*w[i]<0)break;//如果当前情况容量不足，那后面容量肯定也不够，直接跳出换成其他物品
f[j]=max(f[j],f[j-k*w[i]]+k*c[i]);
}
}
}
cout<<f[V];
进行二进制优化，转化成01背包
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++)//把一种物品的数量按照二进制进行拆分，并乘以对应系数
{
int x,y,s,t=1;
cin>>x>>y>>s;//输入费用，单价值，数量
while(s>=t)
{
n1++;
w[n1]=x*t;//乘以系数
c[n1]=y*t;
s-=t;
t*=2;
}
w[++n1]=x*s;//剩余费用
c[n1]=y*s;//剩余价值
}
for(int i=1;i<=n1;i++)
{
for(int j=V;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+c[i]);//01背包解法
}
}
cout<<f[V];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=num[i];j<<=1)
//二进制每一位枚举.
//注意要从小到大拆分
{
num[i]-=j;//减去拆分出来的
new_c[++tot]=j*c[i];//合成一个大的物品的体积
new_w[tot]=j*w[i];//合成一个大的物品的价值
}
if(num[i])//判断是否会有余下的部分.
//就好像我们某一件物品为13,显然拆成二进制为1,2,4.
//我们余出来的部分为6,所以需要再来一份.
{
new_c[++tot]=num[i]*c[i];
new_w[tot]=num[i]*w[i];
num[i]=0;
}
}
单调队列优化
多重背包最普通的状态方程：
f [ i ][ j ] = max ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − k ∗ c [ i ] ] + k∗ w [ i ] )
混合三种背包
问题：
如果把01背包，完全背包，多重背包混合起来。也就是说，有的物品只可以去一次（01背包），有的物品可以无限取（完全背包），有的物品可以取的次数有一个上限（多重背包），应该怎么求解呢？
思路
01背包和完全背包代码中只有v的循环顺序不同，所以可以针对不同的商品类型选用顺序或者逆序的循环即可
for i=1…N
if 第i件物品是01背包
for v = V…0
f [ v ] = max ( f [ v] , f [ v - w [ i ] ] + c [ i ] )
else if 第i件物品是完全背包
for v=0…V
f [ v ] = max ( f [ v ] , f [ v- w [ i ] ] + c [ i ] )
再加上多重背包
将多重背包分成多个01背包然后求解
例题
一个容量为m的背包，现在有n件物品，质量分别是W[i]，价值分别是C[i]，P[i]表示物品的数量，（0说明可以购买无数次，其他数字为购买的最多件数）
代码：
for(int i=1;i<=n;i++)
{
if(完全背包)
{
for(int j=c[i];j<=V;j++)
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
else if(01背包)
{
for(int j=V;j>=c[i];j--)
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
else//否则就是完全背包了
{
for(int j=V;j>=0;j--)
for(int k=1;k<=num[i];k++)
if(j-k*c[i]>=0)
f[j]=max(f[j],f[j-k*c[i]]+k*w[i]);
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)cin>>w[i]>>c[i]>>p[i];
for(int i=1;i<=n;i++)
{
if(p[i]==0)//完全背包
{
for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[j]]+c[i]);
}
else
{
for(int j=1;j<=p[i];j++)//01背包和多重背包
{
for(int k=m;k>=w[i];k--)
{
f[k]=max(f[k],f[k-w[i]]+c[i]);
}
}
}
}
cout<<f[m];
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;
int w[maxn],v[maxn],tot[maxn];
int dp[200010];
int main()
{
int V,n;
scanf("%d%d",&n,&V);
for(int i=1; i<=n; i++)
scanf("%d%d%d",&w[i],&v[i],&tot[i]);
for(int i=1; i<=n; i++)
{
if(tot[i]==0)///完全背包
for(int j=w[i]; j<=V; j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
else///01与多重背包（二进制优化后的多重背包与01背包循环非常相似）
{
int x=tot[i];
for(int k=1; k<x; k<<=1)///此处套用二进制优化的模板
{
for(int j=V; j>=w[i]*k; j--)
dp[j]=max(dp[j],dp[j-w[i]*k]+v[i]*k);
x-=k;
}
if(x)
for(int j=V; j>=w[i]*x; j--)///相当于还剩一个物品未考虑
dp[j]=max(dp[j],dp[j-w[i]*x]+v[i]*x);
}
}
cout<<dp[V];
return 0;
}
京公网安备 11010502036488号