完全背包dp优化

01背包：每个物品只能选择一次
状态转移方程
$$f[i][j]=max(f[i][j],f[i-1][j-v]+w)$$

完全背包：每个物品可以选择无数次

状态转移方程
$$f[i][j]=max(f[i][j],f[i][j-v]+w)$$
其中v表示第i个物品的体积，w表示第i个物品的价值

状态表示
集合：从前i个物品中选，体积不超过j
属性：最大值max
$\Rightarrow f[i][j]$表示只从前i个物品中选，并且体积不超过j的方案的最大价值。
状态计算
对于$f[i][j]$,划分集合，可以划分为很多个
对于第i个物品，我们不选,对应的最大价值:$f[i-1][j]$
对于第i个物品，我们只选1个,对应的最大价值：$f[i-1][j-v]+w$
对于第i个物品，我们只选2个,对应的最大价值：$f[i-1][j-2v]+2w$
不失一般性，选择k个，对应的最大价值:$f[i-1][j-kv]+kw$
只要不超过背包容量m的限制，可以一直选择下去，假设最多放k件物品。
所以，状态计算的方程为上述计算结果的最大值：
$$f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...,f[i-1][j-kv]+kw,)（1）$$

使用变量代换：令j=j-v,此时$f[i][j-v]$表示只在前i个物品中选，背包容量不超过j-v的方案的价值最大值。
有
$$f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,f[i-1][j-3v]+2w,...,f[i-1][j-kv]+(k-1)w,)$$

这里并没有增加一项$f[i-1][j-(k+1)v]+kw$，这是因为背包容量从j变成了j-v，如果背包容量为j时最多可以放k件物品，那么背包容量为j-v时，背包最多可以放k-1件物品。

我们发现
即(1)式的后半部分可以使用f[i][j-v]+w来表示
所以，最后的状态转移方程为
$$f[i][j]=max(f[i][j],f[i][j-v]+w)$$
ac代码（朴素解法）

#include<iostream> #include<cstring> using namespace std;const int maxn=1010;int n,m,dp[maxn][maxn],a[maxn],v[maxn],w[maxn]; int main(){cin>>n>>m;//读入物品数目，背包容量//base case memset(dp,0,sizeof(dp));//数组全部置零for(int i=1;i<=n;i++){//从1开始存cin>>v[i]>>w[i];//读入每件物品的体积和价值}for(int i=1;i<=n;i++)//状态转移for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(j>=v[i])//背包放得下dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);}cout<<dp[n][m]<<endl; }

ac代码（空间优化解法）

主要代码
dp[j-v[i]]小于dp[j],此时从小到大遍历背包容量时，dp[j-v[[i]]已经更新到本层，而不是上一层。满足//相当于dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])
根据闫氏dp分析法， 代码更改之后需要逻辑没变，发现等价后没变。

for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){dp[j]=dp[j];//相当于dp[i][j]=dp[i-1][j]if(j>=v[i])//背包容量为j时的最大价值 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//相当于dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i])}cout<<dp[m]<<endl;//输出背包容量为m时的结果

这样我们就省掉了空间。

#include<iostream> #include<cstring> using namespace std;const int maxn=1010;int n,m,dp[maxn],a[maxn],v[maxn],w[maxn]; int main(){cin>>n>>m;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){//遍历背包容量if(j>=v[i])dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//背包容量为j时的最大价值 }cout<<dp[m]<<endl;//输出背包容量为m时的结果 }

更精简的写法
把遍历背包容量直接提到循环里面for(int j=v[i];j<=m;j++)

#include<iostream> #include<cstring> using namespace std;const int maxn=1010;int n,m,dp[maxn],a[maxn],v[maxn],w[maxn]; int main(){cin>>n>>m;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){cin>>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]);//背包容量为j时的最大价值 }cout<<dp[m]<<endl;//输出背包容量为m时的结果 }

以后写完全背包就写优化后的解法

总结

以上是生活随笔为你收集整理的完全背包dp优化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。