背包初步练习

本篇主要更新AcWing上的两道例题：

11. 背包问题求方案数 - AcWing题库

12. 背包问题求具体方案 - AcWing题库

背包问题求方案数

思路

本题与01背包的模板类型基本一致，具体略有不同。

• 初始化：每个体积下都至少有一个方案：它自己
• 更新方案
  • 如果加上此物品变得比之前大就继承之前的值和方案数
  • 如果和之前的一样就加上此时的方案数和 j-v 的方案数
• 遍历整个价值数组找到最大价值
• 找到最大价值中方案数最多的
• 注意：题目条件是“不超过”背包容量，并不是刚好等于背包容量

代码

void solve()//注意：本题是“不超过”容量
{cin >> n >> m;for(int i=0; i<=m; i++) an[i]=1;//当前体积下的方案数for(int i=1; i<=n; i++){cin >> v >> w;for(int j=m; j>=v; j--){int val=f[j-v]+w;//当前体积下的价值if(val>f[j]){f[j]=val;an[j]=an[j-v];//在体积j-v的基础上更新的价值}else if(val==f[j])//一样的话两个情况都指向这一个an[j]=(an[j]+an[j-v])%mod;}}int maxx=INT_MIN;int ans=0;for(int i=0; i<=m; i++)maxx=max(maxx,f[i]);for(int i=0; i<=m; i++)if(f[i]==maxx) ans=max(an[i],ans);cout<<ans;
}

---

背包问题求具体方案

思路

本题思路和原来背包不太相同，需要外层进行倒序遍历并正序查找

• 由于正向查找的方案基于$i-1$递推只是$i$之前的最优方案而不是所有的最佳方案，所以我们逆向遍历
• 还有就是在判断的时候由于要字典序最小，所以必须正着判断
• 那么现在倒着遍历的话就不能在$i-1$的基础上进行递推了，$i+1$才是它的上一个状态
• 递推式：$dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]]+w[i]);$

代码

void solve()
{cin >> n >> m;for(int i=1; i<=n; i++) cin >> v[i] >> w[i];for(int i=n; i>=1; i--){for(int j=0; j<=m; j++){dp[i][j]=dp[i+1][j];//由于是倒着遍历,所以继承i+1的方案if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);}}for(int i=1,j=m; i<=n; i++)//此时决定是否要选{if(j>=v[i]&&dp[i+1][j-v[i]]+w[i]>=dp[i+1][j]){cout << i << ' ';j-=v[i];}}
}

---

背包问题确实是灵活多变，仅仅掌握模板远远不够。即使是趁着刚刚学完模板的这段时间来写这些题仍然比较吃力，希望能在这周剩下的时间对背包问题的理解更进一步。