Loading... A.M. <!--more--> ---- #### 背包和数位DP ### 背包问题 #### 01背包 * 注意： 1. 虽然一维空间的 0-1 背包不但省空间而且好写，但这并不意味着你可以忘记 0-1 背包二维的写法，有些题目其实会用到，而且输出方案的时候需要保持数组两维 2. 0-1 背包问题有两种：第一种是输出容量不超过 V 的最大收益，而第二种则是输出容量恰好为 V 的最大收益，两者的预处理并不相同 Q：如何计算背包的方案总数与最优方案总数？ ##### 方案总数 for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ f[i][j]=f[i-1][j]; if(j-v[i]>=0) f[i][j]+=f[i-1][j-v[i]]; } } ##### 最优方案总数 $f\[i\]\[j\]$是一个正常01背包，$g\[i\]\[j\]$表示前i个物品选择j体积的物品的最优方案总数。 for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) { f[i][j] = f[i - 1][j]; if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } for (int i = 1; i <= n; i++) for (int j = 1; j <= V; j++) { g[i][j] = g[i - 1][j]; if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i]) g[i][j] += g[i - 1][j - v[i]]; } ##### 例题——Luogu P1489 * Q1：问一共 n 个人分成两队拔河，要求在保证两队人数的差的绝对值不超过1的情况下，输出两队体重差的绝对值的最小值。 * 这题看起来和背包没啥关系，但是仔细思考，可以发现$f\[i\]\[j\]\[k\]$表示前i个人里选j个可否组成k，这样问题就变成了01背包变形，第一维可以省去。 #include<bits/stdc++.h> using namespace std; int n,a[209],sum; bool f[209][80009]; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } f[0][0]=1; for(int i=1;i<=n;i++){ for(int j=n/2;j>=1;j--){ for(int k=sum;k>=a[i];k--){ if(f[j][k]||f[j-1][k-a[i]]) f[j][k]=1; } } } int ans1,ans2; for(int i=sum/2;i>=0;i--){ if(f[n/2][i]) {ans1=i;break;} } ans2=sum-ans1; if(ans1>ans2) swap(ans1,ans2); cout<<ans1<<" "<<ans2; return 0; } * * * #### 完全背包 * 和01背包没啥区别，一个贪心预处理优化： 对于所有 Vi≥Vj，Ci≤Cj 的物品 i，都可以完全扔掉。 对于体积相同的物品只需要留下价值最大的物品。 * 对于随机数据，该优化力度很大。 * * * #### 多重背包 多重背包问题，即每样物品 i ，有自己的体积 Vi，价值 Ci，和数量 Ti，数量并不是无限的，求最大价值 - 思路1：直接把其当做01背包，写出代码。 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=1;k<=t[i];k++){ if(j-k*w[i]>=0) f[j]=max(f[j],f[j-k*v[i]]+k*w[i]); } } } 但很明显，这样做复杂度很高。 \- 思路2：我们注意到我们只关心最终答案是几，而不关心我放进几个物品，所以当$T\_i=3$时，我们可以不必放入3个$(V\_i,W\_i)$，而可以放入一个$(V\_i,W\_i)$和一个$(2V\_i,2W\_i)$，这样仍然可以枚举出放入3个的情况。因此，我们把每个$T\_i$都分解为2的幂次，复杂度可以降到$O(n^2logn)$。 for(int i=1;i<=n;i++){ int tt=t[i]; for(int k=1;k<=tt;k<<=1){ for(int j=v;j>=k*w[i];j--){ f[j]=max(f[j],f[j-k*w[i]]+k*v[i]); tt-=k; } } if(tt>0){ for(int j=v;j>=tt*w[i];j--){ f[j]=max(f[j],f[j-tt*w[i]]+tt*v[i]); } } } * * * #### 分组背包 每一个物品隶属于一个组，每个组里的物品是互斥的，意味着你在一组物品中只能选择一个物品。 for (int i = 1; i <= K; i++) //一共有 K 组 for (int j = V; j >= 0; j--) for (对于第 i 组内的物品k) dp[j] = max(dp[j], dp[j - v[k]] + w[k]) Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏