哈尔滨专门做网站,邢台最近发生的新闻,一学一做演讲视频网站,建设银行招聘官网网站背包问题基本上都是模板题#xff0c;重点#xff1a;弄熟多重背包模板 dp[j]max(dp[j-v[i]]w[i],dp[j]) //核心思路代码#xff08;一维数组版#xff09; dp[i][j]max(dp[i-1][j], dp[i-1][j-v[i]]w[i])//二维数字版 一、 0-1背包
一般输入两个变量#xff1a;体积重点弄熟多重背包模板 dp[j]max(dp[j-v[i]]w[i],dp[j]) //核心思路代码一维数组版 dp[i][j]max(dp[i-1][j], dp[i-1][j-v[i]]w[i])//二维数字版 一、 0-1背包
一般输入两个变量体积亦或者是重量v和价值w
初始化好像不是必须的如果出bug自己又搞不懂是哪里再加上吧
[NOIP2005]采药 登录—专业IT笔试面试备考平台_牛客网
#include iostream
#include vector
using namespace std;
int dp[1000];
int p[101];
int t[101];
int main() {int v,n;cinvn;for(int i0;i101;i){p[i]0;t[i]0;}for(int i0;i100;i){dp[i]0;}for(int i0;in;i){cint[i]p[i];}for(int i0;in;i){for(int jv;jt[i];j--){ //注意是大于等于有等于这里错过好几次dp[j]max(dp[j],dp[j-t[i]]p[i]);}}coutdp[v];
}P1507 NASA的食物计划NASA的食物计划 - 洛谷
来个二维数组版的例子。
#include iostream
#include vector
using namespace std;
int dp[500][500];
int h1[401];
int t1[401];
int k1[501];
int main() {int h,t,n;cinhtn;//初始化 for(int i0;i400;i){h1[i]0;t1[i]0;}for(int i0;i500;i){k1[i]0;}for(int i0;in;i){cinh1[i]t1[i]k1[i];}for(int i0;in;i){for(int jh;jh1[i];j--){for(int kt;kt1[i] ;k--){dp[j][k]max(dp[j][k],dp[j-h1[i]][k-t1[i]]k1[i]);}}}coutdp[h][t];
}
二、 完全背包
一般输入两个变量体积亦或者是重量v和价值w
完全背包的意思就是每个物品可以取无限次0-1背包是每个物品只能取走一次。
完全背包例题3. 完全背包问题 - AcWing题库
#include iostream
#include vector
#includebits/stdc.h
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int main() {int n,v;cinnv;for(int i0;in;i){cinv1[i]w[i];}for(int i0;in;i){for(int jv1[i];jv;j){ //差别在这里dp[j]max(dp[j],dp[j-v1[i]]w[i]);}}coutdp[v];
} 注意可以看出0-1背包和完全背包的问题的解决方案差别不大主要就是在for(int jv……部分的差别。 三、多重背包问题
一般输入两个变量体积亦或者是重量v、价值w和数量s
背包问题中最难的了结合了0-1背包和多重背包的特点简单来说就是某个物品可以取s次有了次数限制。
常规思路就是拆分成份重新构成0-1背包问题。
例题4. 多重背包问题 I - AcWing题库
#include iostream
#include vector
#includebits/stdc.h
using namespace std;
int dp[1001];
int v1[1001];
int w[1001];
int s[1001];
int main() {int n,v;cinnv;for(int i0;in;i){cinv1[i]w[i]s[i];}for(int i0;in;i){while(s[i]!0){ //监控数量for(int jv;jv1[i];j--){ //0-1背包处理dp[j]max(dp[j],dp[j-v1[i]]w[i]);}s[i]--;}}coutdp[v];
}
可以看到for(int jv……这部分的处理和0-1背包的处理逻辑一样。就是在外面增加一个while监控数量的变化即可。整体还是在for(int i0;in;i){框架下。
上述的微小改进只适用于处理小范围数据集数据集一大一两千就会超时此时就需要改进算法了参考下题
数据量大的情况5. 多重背包问题 II - AcWing题库 二进制优化是基于这样的事实 任意正整数可以表示为2的幂之和。 利用这一点我们可以将每种物品的数量拆分成几个二进制的组件从而将多重背包问题转换为0-1背包问题的多个实例。 二进制拆分挺麻烦的……要加里面我写了一版有的用例没有过还需要再背2024年5月6日
#include bits/stdc.h
using namespace std;
int dp[2102];
int v1[2101];
int w[2101];
int s[2001];int main() {int n,v;cinnv;for(int i0;in;i){cinv1[i]w[i]s[i];}for(int i0;in;i){if(s[i]*v1[i]v){ //份数乘以重量 大于 容量采取完全背包。 for(int jv1[i];jv;j){dp[j]max(dp[j],dp[j-v1[i]]w[i]);}}else{// 二进制拆分处理多重背包问题for(int k1;s[i]0;kk*2){if(ks[i]){// 当拆分块大于剩余数量时调整k为剩余数量ks[i];}int totalvk*v1[i];int totalwk*w[i];for(int jv;jtotalv;j--){//0-1背包处理 dp[j]max(dp[j],dp[j-totalv]totalw);}s[i]s[i]-k;}}}coutdp[v];return 0;
}
四、分组背包问题
分组背包问题9. 分组背包问题 - AcWing题库
就是分组每个组只能取一个背包。这个模板没背过下次记得背2024年5月6日
#include bits/stdc.h
using namespace std;
int dp[102];
int v1[101];
int w[101];int main() {int n,v,z;cinnv;for(int i0;in;i){cinz;for(int j0;jz;j){ cinv1[j]w[j];}for(int kv;k0;k--){for(int j0;jz;j){if(kv1[j]){dp[k]max(dp[k],dp[k-v1[j]]w[j]); }}}}coutdp[v];return 0;
}
