介绍01背包、多重背包、完全背包等。这几种简单基础的背包。麻烦的基本都是它们的延伸。
01背包 二维数组的坑！！一维数组的便利
01背包
例题 HDU2602 捡骨头
有一个大小为M的背包，有n件物品，每件物品都有一个重量w和一个价值v，在n件物品中拿出几件放在背包里，要求在满足重量之和小于M的情况下，物品的价值之和最大。每件物品都只能拿至多一次。
状态转移方程：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
分析方程，dp[i][j]表示在只考虑前i件物品的情况下，背包大小为j时的最优解。在新加入物品a[i]时，这件物品，要么拿，要么不拿，在这两种情况里选最优。不拿的话，最优解为dp[i-1][j]；拿的话，最优解为dp[i-1][j-w[i]]+v[i]。
二维数组作法
for (int i=1;i<=n;i++){
for (int j=1;j<=M;j++){
if (a[i]>j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}踩过的坑：二维数组不同于滚动数组，一定要把a[i]<j的情况下的数组也更新一下！ 否则会出错。。
。
滚动数组作法
有时候NM的值很大时，导致无法开出这么大的二维数组，这时候就要用到滚动数组了。dp[M].
dp[j]的值表示在已考虑过的前i件物品中，背包大小为j时的最优解。
for (int i=1;i<=n;i++){
for (int j=M;j>=a[i];j--){
dp[j] = max(dp[j],dp[j-a[i]]+v[i]);
}
}注意滚动数组中背包大小的值j一定要从大到小循环，因为从大到小的话，对于k<j，dp[k]，也就是代码中的dp[j-a[i]]，是前i-1件物品的最优解。如果从小到大循环，dp[k]是已经包含可第i件物品的最优解，不能再次考虑，否则dp[j-a[i]]这个解可能已经把a[i]包含了一次了。
完全背包
采药 洛谷P1048
完全背包，就是在01背包的基础上，每件物品可以拿无限次。
只需在01背包的方程上小做改动即可。
dp[i][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])
把i-1变成i就行了。i-1的含义是第i件物品拿了就不能再拿了，只能考虑前i-1件。那现在每件物品可以拿无限次，i-1改成i就ok了。
二维数组作法
for (int i=1;i<=n;i++){
for (int j=1;j<=M;j++){
if (a[i]>j)
dp[i][j] = dp[i-1][j]; //这里注意下如果j<a[i],也就是第i件物品1件都拿不下时，只能考虑前i-1件。
else
dp[i][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}滚动数组作法
把01背包的代码中内层循环从大到小遍历，改成从小到大遍历即可。
从小到大遍历，就是说这件物品已经拿过了，还可以再拿的。
for (int i=1;i<=n;i++){
for (int j=a[i];j<=M;j++){
dp[j] = max(dp[j],dp[j-a[i]]+v[i]);
}
}多重背包
硬币 HDU2844
这个倒是~有点复杂的~，在01背包的基础上，每件物品拿的次数是有限的，限制不再是1，也不是无限次，而是有个有穷值k。
这种情况下，也可以转换成01背包来解决，把这个最多能拿k次的一件物品，分解成最多能拿1次的k件不就行了。
但是当k之和很大时，这样就不现实了，会导致数据量很大。
这里应用到了一个数论中的小知识：2^0,2^1,……,2^n这些数可以组合成2^{n+1}-1内的任意一个数。
那么把k分解成2^0,2^1,……,2^n,k-2^n就行了，大大缩减了数据量，k->logk。2^{n+1}-1<=k<2^{n+2}-1
混合背包
就是三种背包的混合，在完全掌握上述三种背包后，我们可以发现，一件物品，他拿的次数最终可以化简为至多拿1次、可以拿无数次，就这两种情况，然后对于这两种情况的循环遍历做个区分就行了。
vis[i]=1时表示可以拿无限次，vis[i]=0时表示可以拿1次。
二维数组
for (int i=1;i<=n;i++){
if (vis[i]){
for (int j=1;j<=M;j++){
if (a[i]>j) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
}
}else{
for (int j=1;j<=M;j++){
if (a[i]>j) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}
}
}滚动数组
就是滚动方式变了一下。
for (int i=1;i<=n;i++){
if (vis[i]){
for (int j=w[i];j<=M;j++)
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}else{
for (int j=M;j>=w[i];j--)
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}例题
例题 HDU2602 捡骨头 01背包
采药 洛谷P1048 完全背包
硬币 HDU2844 多重背包
硬币 HDU2844
有各种面值的硬币若干个，问能组成多少个小于M的整数值。
转化成01背包后，判断dp[N][j]是否等于j即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int dp[100005];
int a[105],b[105],v[10000];
int main(){
int n,m,cnt,ans;
while (~scanf ("%d %d",&n,&m) && n){
cnt = ans = 0;
//memset(dp,0,sizeof dp);
//memset(v,0,sizeof v);
for (int i=1;i<=n;i++) scanf ("%d",&a[i]);
for (int i=1;i<=n;i++) scanf ("%d",&b[i]);
for (int i=0;i<=m;i++) dp[i] = 0;
for (int i=1;i<=n;i++){
int j;
for (j=1;(j<<1)-1<=b[i];j<<=1)
v[++cnt] = a[i] * j;
j >>= 1;
if (b[i]>2*j-1) v[++cnt] = a[i] * (b[i]-2*j+1);
}
for (int i=1;i<=cnt;i++) for (int j=m;j>=v[i];j--)
dp[j] = max(dp[j],dp[j-v[i]]+v[i]);
for (int i=1;i<=m;i++) if (dp[i]==i)
ans++;
printf ("%d\n",ans);
}
return 0;
}
0 条评论