背包九讲(1)——01背包
有n种物品，每种只有一个。第i种物品的体积为vi，价值为wi。选一些物品装入到一个容量为C的背包中，使得在总体积不超过m的情况下使得背包内物体总价值尽量大
状态转移首先我们不难发现影响决策的因素有两个：
第i个物品装或者不装 使用j(j<=C)容量后得到的最大价值实际上容量是一个有序的枚举过程，但是每个物品选或不选是影响决策的主要因素，下面有两种对称的状态定义：
逆序枚举
设dp(i,j)表示将第i,i+1,i+2,…,n个物品装入容量为j的背包中的最大价值，则：
dp(i,j) = dp(i+1,j)
dp(i,j) = max { dp(i,j)，dp(i+1,j-v[i]) + w[i] }
上述状态转移方程的含义是在容量为j时是否选择第i个物品会使答案更大，不选择则是i+1且容量为j的状态，选择的话则是在更新状态dp(i+1,j-v[i])——j容量减少v[i]而价值增加w[i]
我们需要逆序枚举第i个物品，j的循环是无关紧要的，因为都是i+1对应j的状态转移而来，互不影响
边界处理则是初始化为0，最终的答案是dp(1,C)
int v[1005],w[1005],d[1005][1005];
cin>>n>>C;
for(int i=1;i>v[i]>>w[i];
for(int i=n;i>=1;i--){
d[i][j]=d[i+1][j]; //此处的更新一定不能省略，当前状态必须首先更新为上一个状态
if(j>=v[i]) d[i][j]=max(d[i][j],d[i+1][j-v[i]]+w[i]); //这里的更新是有条件的因此不能将d[i+1][j]写在此处
}
}
cout<<d[1][C]<<endl;
顺序枚举
这是广为使用的一种解法：
设dp(i,j)表示将第1,2,3,…,i个物品装入容量为j的背包中的最大价值，则：
dp(i,j) = dp(i-1,j)
dp(i,j) = max { dp(i,j)，dp(i-1,j-v[i]) + w[i] }
上述状态转移方程的含义是在容量为j时是否选择第i个物品会使答案更大，不选择则是i-1且容量为j的状态，选择的话则是在更新状态dp(i-1,j-v[i])——j容量减少v[i]而价值增加w[i]
边界处理仍是初始化为0，最终的答案是dp(n,C)
int v[1005],w[1005],d[1005][1005];
cin>>n>>C;
for(int i=1;i>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=0;j=v[i]) d[i][j]=max(d[i][j],d[i-1][j-v[i]]+w[i]);
}
}
上述两种方法其实存在的细微差别，即第二种方法可以边输入边计算，而不必保存v和w，因此建议熟练使用第二种思路：
int d[1005][1005];
cin>>n>>C;
for(int i=1,v,w;i>v>>w;
for(int j=0;j=v[i]) d[i][j]=max(d[i][j],d[i-1][j-v]+w);
}
}
滚动数组
这里我们以顺序枚举的方法空间优化为例，首先放出代码：
最终的答案就是f[C]
int f[1005];
for(int i=1,v,w;i>v>>w;
for(int j=C;j>=v;j--){ //这里必须逆序
f[j]=max(f[j],f[j-v]+w);
}
}
为什么这样做是正确的？最主要的是为什么里层的循环必须逆序？
首先看二维数组的主要状态转移过程：
这里的数组是从上到下从左到右计算的，每次先将第i-1层状态转移到第i层，并根据v[i]更新若干个dp(i-1,j-v[i])
如果变成一维数组，f[i]保存的就是f[i-1]的值，而f[j-w]里保存的f(i-1,j-w)的值，这样的话如果更新f[j]为f[j-v]+w，那么从f(i-1,j-v)的状态（即现在的f[j-v]），更新了后面列的状态实际上覆盖掉了原来的f(i-1,j)，而且使得f[j-v]的状态得以保留
总的来说是后面列的更新依赖于前面的列却不影响前面的列，因此滚动数组的优化得此而来
模板题Acwing背包九题
#include
#include
Happig丶
原创文章 206获赞 19访问量 1万+
关注
私信
展开阅读全文
作者：Happig丶
