常用背包dp模板（未完待续）
这里是作者的留言板部分板子优化中...；
你好哇，我是flypig114；
先说一句：本人仅在博客园发表博客，其他皆为盗版；
可能某些人能看出上面那句是什么意思，我也不多说了；
代码里有变量（只不过最近会改变量名使其更正规）数组的注释，so...不多废话，直接上正题！；
01背包
<blockquote>这里是题目AWA：
有\(N\)件物品和一个容量是\(M\)的背包。每件物品只能使用一次。第 \(i\)件物品的体积是\(w\)，价值是\(v\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入格式
第一行两个整数，\(N\)，\(M\)，用空格隔开，分别表示物品数量和背包容积。接下来有 \(M\)行，每行两个整数\(wi\),\(vi\)，用空格隔开，分别表示第\(i\)件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
\(0 n >> m; for (i = 1; i > w >> v; } //进行处理 for (i = 1; i = 0; j--)//从背包容量开始，保证每个物品都考虑过 { if(j>=w)//判断是否可以放入 { dp = max(dp] + v, dp);//判断是否放入，dp]+v更大则放入 } else { dp = dp;//不放入 } } //结束首战告捷 cout > n >> m; for (i = 1; i > w >> v; } //重中之重（好像就这里改了） for (i = 1; i = 0; j--) { if(j>=w) { dp = max(dp] + v, dp); } } } //可以输出了 coutv >> w;}//完全背包启动！for (i = 1; i > n; for (i = 1; i > w >> v >> s; } //熟悉的流程 for (i = 1; i = v; j--) //倒序是为了防止重复计算 { for (k = 1; k * vn; for (i = 1; i > v >> w >> s; } //拆分方式更加优美 for (i = 1; i = s * v; j--) { dp = max(dp, dp * v] + s * w); } } //我的回合！输出！ cout > n >> m; for (i = 1; i > v >> w >> s; } for(i=1;i
页:
[1]