DPの奇妙冒险02：背包
如果你被一道水题暴切，那么就来水水博客吧
背包 DP ，
就是以背包问题为背景的 DP . 废话
万丹（蓝书上没有定义）
背包问题一般有多个限制维度与一个定义最优性的维度，最终结果为满足限制条件的情况下的最优解。
话不多说，言归正传——
1、0/1背包
最朴实的背包……
不过作为模板（采药），还是有必要放一下代码的。
（a[i].t表示时间，a[i].v表示价值）
for(int i=1;i<=m;i++){
for(int j=1;j<=t;j++){
if(a[i].t>j){
vv[i][j]=vv[i-1][j];
}else{
vv[i][j]=max(vv[i-1][j],vv[i-1][j-a[i].t]+a[i].v);
}
}
}第一次优化：降维打击 空间优化，滚动数组
改良后代码：
for(int i=1;i<=m;i++){
for(int j=t;j>=a[i].t;j--){//另，循环边界与循环顺序发生了变化。
vv[j]=max(vv[j],(vv[j-a[i].t]+a[i].v));
}
}2、完全背包
最朴实的基础上改编的最暴力的背包……
不过作为模板（疯狂的采药），还是有必要放一下代码的。
（a[i].t表示时间，a[i].v表示价值）
for(int i=1;i<=sm;i++){
for(int j=a[i].t;j<=st;j++){//仅仅改了循环顺序而已
vv[j]=max(vv[j],(vv[j-a[i].t]+a[i].v));
}
}另，无意间找到了这么一道题，很水但很有趣。
3、有些题：
题目中并没有直接的w轴（资源轴）与v轴（价值轴），而是隐藏在了同一个条件中。 比如，
这道题
想不到吧，这是背包哦~
正解：每一天都凌晨买进一些纪念品，午夜卖出当天买的纪念品，如果每天都按照最优方式进行，最终答案也是最优解。
那么问题就转移成了：如何在（每一天内的）有限金币内买到利润最大的纪念品。
w轴：纪念品的价格。
v 轴：纪念品的利润。
Solved。
4、多维背包
本质上是一样的。
只不过限制条件++，不再只有一种资源了……
比如这道题
for(int i=1;i<=n;i++){
for(int j=x;j>=c[i];j--){
for(int p=m;p>=b[i];p--){
vv[j][p]=max(vv[j][p],(vv[j-c[i]][p-b[i]]+a[i]));
}
}
}或者是评判标准++，不再只有一种价值了……
即“次要性DP”。
比如这道题
鉴于我还没写，所以就当题解搬运工吧
用两个DP数组来状态转移，比如如下代码：
虽然马蜂是真的ugly
for (int i = 1; i <= n; ++i)
for (int j = m; j >= rmb[i]; --j)
for (int k = r; k >= rp[i]; --k) {
// 如果能泡到更多妹子
if (dpN[j][k] < dpN[j - rmb[i]][k - rp[i]] + 1) {
dpN[j][k] = dpN[j - rmb[i]][k - rp[i]] + 1; // 数量++
dpT[j][k] = dpT[j - rmb[i]][k - rp[i]] + t[i]; // 花费的时间加进去
}
else if (dpN[j][k] == dpN[j - rmb[i]][k - rp[i]] + 1)
// 如果能泡到同样多的MM，选择时间最少的方案
dpT[j][k] = min(dpT[j][k], dpT[j - rmb[i]][k - rp[i]] + t[i]);
}或者使巧劲，
/*
本题的优化目标有两个
1）让xx的女朋友最多
2）让xx在女朋友最多的情况下，花费时间最少
我们可以设xx最后的女朋友数最后为 a ，xx最后花费的时间为t,
则我们可以把最小化目标定为
M * a - t
其中M是一个很大的正整数。
在这道题目里xx的女朋友个数 对 答案的影响
比xx的花费时间对答案的影响大的多
（或者说起决定性作用）
因此，我们要确保xx的女朋友数对答案的影响的百分比 远大于 xx的花费时间 对答案的影响
事实上，你只需要确保
M > 所有的 xx花费的时间 总和 tsum
/*
这样，当a不同的时候，a对答案起决定性作用，
只有当a相同的时候，t 才会对答案起决定性作用
*/
*/
for(int i = 1; i <= N; i++){
w[i]-1000000-w[i];
for(int j = cmax; j >= c[i]; j--){
for(int k = rpmax; k >= rp[i]; k--){
f[j][k] = max(f[j - c[i]][k - rp[i]] + w[i], f[j][k]);
}
}
}
cout<<1000000-f[cmax][rpmax]%1000000;5、多重背包（二进制拆分）
一点也不朴实的背包……
不过作为模板（庆功会），还是有必要放一下代码的。
for(int i=1;i<=n;i++){
cin>>a>>b>>c;
int k=1;
while(c>k){
tn++;
v[tn]=k*a;
w[tn]=k*b;
c-=k;
k<<=1;
}
tn++;
v[tn]=c*a;
w[tn]=c*b;
}//拆分完之后就可以直接做啦~~~
//分完之后，原来的物品数量的组合为（1、2、4、8……以及剩下的部分）6、 分组背包
一点也不易理解的背包……
不过作为模板（分组背包），还是有必要放一下代码的。
for(int i=1;i<=t;i++){//一共有t组物品
for(int j=m;j>=1;j--){对于每一组，求出此时0/1背包的最大利用值
for(int p=1;p<=tn[i];p++){//第i组有tn[i]种物品
if(j>=a[i][p]) dp[j]=max(dp[j],dp[j-a[i][p]]+b[i][p]);
}
}
}写在最后
《关于你想水水博客却发现1 mol 不会做的黄题……》
首尾呼应
写在更后
刚写完博客就碰见个背包……
虽然挺好想的，但细节多的一批
是这道题
祝你们好运[微笑]
本蒟蒻提交了16次才过