网站开发报告,如何给wordpress上传较大视频,个人邮箱登录登录入口,wordpress宝宝网商城免费模板下载我们已经学过好久好久的动态规划了#xff0c;动态规划_Peter Pan was right的博客-CSDN博客
那么#xff0c;我用一张图片来概括一下背包问题。 大家有可能比较疑惑#xff0c;优化决策怎么优化呢#xff1f;答案是#xff0c;滚动数组#xff0c;一个神秘而简单的东西… 我们已经学过好久好久的动态规划了动态规划_Peter Pan was right的博客-CSDN博客
那么我用一张图片来概括一下背包问题。 大家有可能比较疑惑优化决策怎么优化呢答案是滚动数组一个神秘而简单的东西。
01背包
题目小偷来你家他带的包只能装c斤的财务。你家有n种财务分别重w1、w2......wn斤价值分别为v1、v2......请输出能拿走的最大总价值
大家思考一下状态定义和状态转移方程。
额……
状态定义
f[i][j]用前i个物品每个物品只能选或不选满足重量和小于等于j的所有选法中价值最高的那个方案。最终答案f[n][c]
状态转移方程
首先我们分两种情况讨论1.选i 2.不选i
1。 此时我们重量和会变小w[i]但是价值会增加v[i]f[i][j]f[i-1][j-w[i]]v[i]
2。 此时物品数减1f[i][j]f[i-1][j]
最后再取最大值得到状态转移方程f[i][j]max(f[i-1][j],f[i-1][j-w[i]]v[i])
代码①
for(int i1;in;i) cinw[i]v[i];
for(int i1;in;i){for(int j1;jc;j){if(w[i]j) f[i][j]f[i-1][j];else f[i][j]max(f[i-1][j],f[i-1][j-w[i]]v[i]);}
}
coutf[n][c]endl;
有点费空间要开滚动数组
代码②
滚动数组给大家看个图 我们发现dp[i][j]这一格只需要i-1这一行i-2、i-3……都不需要。题目如果并没有要求中间的状态比如输出背包的方案我们就可以将其省略来节省空间的使用。所以我们可以只用一维数组dp[j]来记录数据dp[i][j]的状态在更新的过程中不断用新的数据dp[j] (dp[i][j]) 覆盖掉旧的数据dp[j]dp[i-1][j]。大家听懂了吗
代码呢
#include bits/stdc.h
using namespace std;
const int MAXC2009;
int n,c,w,v,f[MAXC];
int main(){cincn;for(int i1;in;i){cinwv;for(int jc;jw;j--)f[j]max(f[j],f[j-w]v);}coutf[c]endl;return 0;
}
大家可能会疑惑为什么第二层循环要倒着推啊我给出一个解释。我们每次计算dp[j] (即dp[i][j]) 的时候都会需要dp[j-w[i]] (即dp[i-1][j-w[i]])的值。所以如果我们正序计算那么dp[j-w[i]]就已经更新了 即用过之前的背包了与每个背包只能用1次不符。那么这不就是完全背包要的吗
完全背包
题目小偷来你家他带的包只能装c斤的财务。你家有n种财务每种数量无限多分别重w1、w2......wn斤价值分别为v1、v2......请输出能拿走的最大总价值
题解请看01背包这里只给出代码
cincn;
for(int i1;in;i){cinwv;for(int jw;jc;j)f[j]max(f[j],f[j-w]v);
}
coutf[c]endl;
分组背包 分组01与普通01的区别就是分组01有两组策略1.选择本组的某一件 2.一件不选 所以说分组背包编码很麻烦
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll G19;
const ll N39;
const ll MAXV209;
ll c,n,g,f[MAXV];
vectorll w[G],v[G];
int main(){cincng;for(ll i1;in;i){ll ww,vv,p;cinwwvvp;w[p].push_back(ww);v[p].push_back(vv);}for(ll i0;ig;i){//枚举组号for(ll jc;j0;j--){//枚举载重for(ll k0;kw[i].size();k){//枚举物品if(jw[i][k]) f[j]max(f[j],f[j-w[i][k]]v[i][k]);}}}coutf[c]endl;return 0;
}
多重背包 多重背包怎么办呢这里我们要采用二进制拆分。 就是……这样
void bb01(int w,int v){for(int jc;jw;j--)f[j]max(f[j],f[j-w]v);
}
int main(){cinnc;for(int i1;in;i){cinwvs;for(int k1;ks;s-k;k*2) bb01(k*w,k*v);if(s) bb01(s*w,s*v);}coutf[c]endl;return 0;
}
简单吧其实为什么这里我都没有进行仔细的讲解是因为……不会再多思考思考01背包和图片。
混合背包 大家试着写写。大家有兴趣的话可以去往上搜搜“背包九讲”。
希望这些对大家有用三连必回
