ACM模板 | 背包问题模板总结
背包问题模板
01 背包问题
一维数组（滚动数组）模板
for(int i = 1; i <= m; ++i){ //小于等于总个数，从 1 开始for(int j = T; j >= 0; --j){ //逆序，从总容量开始递减if(j >= good[i].t){ //单个物品体积不超过背包容量 dp[j] = max(dp[j], dp[j-good[i].t]+good[i].w); //减去单个物品体积后的 dp + 这个物品的重量}}
}
例题
- 洛谷 P1048 采药
- 洛谷 P1049 装箱问题
- 洛谷 P1060 开心的金明
- 洛谷 P1164 小A点菜
完全背包问题
一维数组（滚动数组）模板
for(int i = 1; i <= m; ++i){ //小于等于总个数，从 1 开始for(int j = good[i].t; j <= T; ++j){ //完全背包：顺序 dp[j] = max(dp[j], dp[j-good[i].t]+good[i].w); //减去单个物品体积后的 dp + 这个物品的重量}
}
例题
- 洛谷 P1616 疯狂的采药
带附件的背包问题
模板（以两个附件为例）
for(int i = 1; i <= m; ++i){ //i <= 可选的物品种类，从1开始 for(int j = n; j >= 0; --j){ //j = 总钱数 if(j >= good[i][0].v){ //只选主件 dp[j] = max(dp[j], dp[j-good[i][0].v]+good[i][0].w); //不选当前件，选择当前件所以要花费当前物品的费用，再加上总价值 }if(j >= good[i][0].v+good[i][1].v){ //选主件+附件1 dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v] + good[i][0].w+good[i][1].w); }if(j >= good[i][0].v+good[i][2].v){ //选主件+附件2 dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][2].v] + good[i][0].w+good[i][2].w);}if(j >= good[i][0].v+good[i][1].v+good[i][2].v){ //都选 dp[j] = max(dp[j], dp[j-good[i][0].v-good[i][1].v-good[i][2].v]+ good[i][0].w+good[i][1].w+good[i][2].w);} }
}
例题
- 洛谷 P1064 金明的预算方案
多重背包
模板
//完全背包
void CompletePack(int v, int w, int m){for(int i = v; i <= m; ++i){dp[i] = maxx(dp[i], dp[i-v]+w);}
}//01背包
void ZeroOnePack(int v, int w, int m){for(int i = m; i >= v; --i){dp[i] = maxx(dp[i], dp[i-v]+w);}
} //多重背包
void MultiPack(int v, int w, int m,int c){if(v*c >= m){CompletePack(v,w,m); }else{int k = 1;while(k < c){ZeroOnePack(k*v,k*w,m);c -= k;k *= 2;}ZeroOnePack(c*v, c*w, m);}
}
例题
- HDU 2844 Coins
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！