本文最后更新于634 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com
完全背包实际上与01背包没什么区别,我们知道01背包的问题是这么描述的:
有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
而这跟完全背包不同的地方在于完全背包的每种物品有无限个,01背包每种物品只有一个。
分析
那我们在考虑第i个物品时,除了要考虑该物品取不取,还要考虑该物品取多少个;
我们可以在01背包的基础上,再枚举该物品要取多少个;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k*v[i]<=j;k++)//对物品的数量进行枚举
{
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);
}
}
}
你可能发现了,为什么是dp[i][j]而不是像01背包一样是dp[i-1][j]?
其实真正的状态转移方程是这样的:
max(dp[i-1][j],dp[i-1][j-v[i]*k]+w[i]*k)
当k=0时,dp[i][j]=max(dp[i-1][j],dp[i-1][j]),实际上是一样的,所以dp[i-1][j-v[i]*k]+w[i]*k就已经包括了
dp[i-1][j];又因为有这已成循环的存在,max里面的dp[i][j]也是必须要有的,此时的dp[i][j]记录的是k-1个i物品的总价值;
但如果这么写,时间复杂度大概为O(nm2),数据稍微强一点,肯定过不去;
优化
我们把方程展开之后发现:
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*1]+w[i]*1,dp[i-1][j-v[i]*2]+w[i]*2,...,dp[i-1][j-v[i]*k]+w[i]*k);
dp[i][j-v[i]]=max( dp[i-1][j-v[i]], dp[i-1][j-v[i]*2]+w[i], ... ,dp[i-1][j-v[i]*k]+w[i]*(k-1));
比对之后我们可以发现:
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
我们就去掉了一层循环
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
dp[i][j]=dp[i-1][j];
if(v[i]<=j)dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
}
我们同样可以通过滚动数组将其变成一维的,最终代码就成了这样:
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}