网站里自已的微信联系如何做,有赞小程序开发平台,怎样更新网站快照,摄影设计说明万能模板目录 一、01背包问题
二、完全背包问题
三、多重背包问题
四、多重背包问题#xff08;优化版#xff09;
五、分组背包问题 一、01背包问题
01背包问题就是有N件物品#xff0c;一个空间大小为V的背包#xff0c;每个物品只能使用一次#xff0c;使得背包中所装物品…目录 一、01背包问题
二、完全背包问题
三、多重背包问题
四、多重背包问题优化版
五、分组背包问题 一、01背包问题
01背包问题就是有N件物品一个空间大小为V的背包每个物品只能使用一次使得背包中所装物品的价值总和最大。 如图所示使用一个二维数组来存放从前i个物品中取总体积不超过j的包中价值最大值。 根据图二所示我们可以将每次dp到的情况分为两种一种是选择第 i 件物品另一种是不选择第 i 件物品。
不含 i 就是从0~i-1中选择体积不超过 j 的物品也就是含 i 即从 1 ~ i 中选包含 i且总体积不超过 j。可以先把第 i 个物品拿出来即从第 1 ~ i-1中选且总体积不超过 j-v[i]也就是
最终f[ i ][ j ] max(f[ i-1 ][ j ], f[i-1][j-v[ i ]] w[ i ] 例题https://www.acwing.com/problem/content/2/
朴素做法
#includeiostream
using namespace std;
const int N1010;
int v[N],w[N];
int f[N][N];int main()
{int n,m;cinnm;for(int i 1;in;i) cinv[i]w[i];for(int i1;in;i){for(int j1;jm;j){f[i][j]f[i-1][j];if(jv[i])//可以装的下{f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}}}coutf[n][m];return 0;
}
优化 f[i] 只用到了 f[i-1] 这一层即 f[i-2] 到 f[0] 对 f[i] 是没有用的所以第二层循环可以直接从 v[i] 开始
for (int i 1; i n; i) {for (int j v[i]; j m; j) {f[i][j] max(f[i][j], f[i - 1][j - v[i]] w[i]);}
} 从二维优化成一维空间优化
如果直接删除掉 f[i] 这一维即
f[j] max(f[j], f[j-v[i]] w[i]);
但是这样直接删掉是错误因为j是递增的。
原式f[i][j] max(f[i][j], f[i - 1][j - v[i]] w[i]);
改成一维f[j] max(f[j], f[j - v[i]] w[i]);
由于 f[i][] 只跟上一状态f[i - 1][]有关 上面两个式子 这一状态左 上一状态右
即 f[i][j] 是由 f[i - 1][j - v[i]] 推出来的 现在进行空间优化那么必须要保证 f[j] 要由 f[j - v[i]] 推出来的。
如果j层循环是递增的则相当于 f[i][j] 变得是由 f[i][j - v[i]] 推出来的 而不是 f[i - 1][j - v[i]] 推出来的。 优化后代码
#includeiostream
using namespace std;
const int N1010;
int v[N],w[N];
int f[N];int main()
{int n,m;cinnm;for(int i 1;in;i) cinv[i]w[i];for(int i1;in;i){for(int jm;jv[i];j--){f[j]max(f[j],f[j-v[i]]w[i]);}}coutf[m];return 0;
}
二、完全背包问题
完全背包不同于01背包的是每件物品都是无限使用的。 如图所示与01背包相似的是每次选择0,1,2,3,4,5....k个
不选时仍是 f[ i-1][ j ]
选择k件时是 f[ i-1][ j-k*v[i]] k*w[i]
也就是 f[ i-1][ j-k*v[i]] k*w[i] 例题https://www.acwing.com/problem/content/3/
朴素写法
#includeiostream
using namespace std;const int N1010;
int n,m;
int v[N],w[N],f[N][N];int main()
{cinnm;for(int ii;in;i) scanf(%d%d,v[i],w[i]);for(int i1;in;i){for(int j1;jm;j){for(int k0;k*v[i]j;k){f[i][j]max(f[i][j],f[i-1][j-k*v[i]]w[i]*k);}}}coutf[n][m];return 0;
} 优化 在对完全背包问题优化时我们由图公式可知f[i][j]可以简化为max(f[i-1][j],f[i][j-v]w) 优化后代码
#include iostream
#include algorithmusing namespace std;const int N1010;
int f[N];
int v[N],w[N];
int n,m;
int main()
{cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i){for(int jv[i];jm;j){f[j]max(f[j],f[j-v[i]]w[i]);}}coutf[m];return 0;
}
三、多重背包问题
多重背包问题相较于之前的问题就是每个物品是有限s个。 例题https://www.acwing.com/problem/content/4/
#includeiostream
using namespace std;
const int N110;int n,m;
int s[N],v[N],w[N];
int f[N][N];int main()
{cinnm;for(int i1;in;i) cinv[i]w[i]s[i];for(int i1;in;i){for(int j0;jm;j){for(int k0;ks[i]j(k*v[i]);k){f[i][j]max(f[i][j],f[i-1][j-v[i]*k]w[i]*k);}}}coutf[n][m];return 0;
} 四、多重背包问题优化版 首先我们以之前完全背包问题的优化方法尝试使用另一个表达式来代替但是结果如图所示不是很好解决。
二进制法优化二进制优化的方法在于使用二进制的表示方式来代替每个物品的个数当某件物品的个数很多的时候无需从1遍历循环到n可以将其分解成个位权来表示。
为了方便理解举个例子
如果要拿1001次苹果传统就是要拿1001次二进制的思维就是拿7个箱子就行分别是装有512、256、128、64、32、8、1个苹果的这7个箱子,这样一来1001次操作就变成7次操作就行了。
但是要注意的一点是如果某件物品的个数不是二次幂减一就将前一位的值与s差值记为下一个位权。这样就可以表示0~s之内的所有数了。
然后就将问题分解成为了01背包问题。
例题https://www.acwing.com/problem/content/5/ #includeiostream
using namespace std;const int N11010,M2010;
int v[N],w[N];
int f[N];int main()
{int n,m;cinnm;int cnt0;while(n--)//初始化v[] w[]{int a,b,s;cinabs;int k1;while(ks){cnt;v[cnt]a*k;w[cnt]b*k;s-k;k*2;}if(s0){cnt;v[cnt]a*s;w[cnt]b*s;}}ncnt;//01背包for(int i1;in;i){for(int jm;jv[i];j--){f[j]max(f[j],f[j-v[i]]w[i]);}}coutf[m];return 0;
}
五、分组背包问题
分组背包问题的不同于之前背包问题的地方在于分组背包是将物品分成几组然后再在每组里面选择一个物品并且每组只能选择一个物品。 这里的dp状态计算与之前的也有所不同这里表示的是第i组选哪一个f[i-1][j]是表示不选择这一组的物品f[i-1][j-v[i,k]]w[i,k]表示的是这一组中选择哪一个。
例题 https://www.acwing.com/problem/content/9/
#includeiostream
using namespace std;const int N110;
int n,m;
int s[N],v[N][N],w[N][N];
int f[N];int main()
{cinnm;for(int i1;in;i){cins[i];for(int j1;js[i];j){cinv[i][j]w[i][j];}}for(int i1;in;i){for(int jm;j0;j-- ){for(int k0;ks[i];k){if(v[i][k]j){f[j]max(f[j],f[j-v[i][k]]w[i][k]);}}}}coutf[m];return 0;
}
