浙江省建设厅网站资质迁移,广西壮族自治区博物馆,深圳品牌设计工作室,建筑木工招聘平台1.01背包问题 我们首先定义一个二维数组f#xff0c;其中f[i][j]表示在前i个物品中取且总体积不超过j的取法中的最大价值。那么我们如何得到f[i][j]呢#xff1f;我们运用递推的思想。由于第i个物品只有选和不选两种情况#xff0c;当不选第i个物品时#xff0c;f[i][j]f[i…
1.01背包问题 我们首先定义一个二维数组f其中f[i][j]表示在前i个物品中取且总体积不超过j的取法中的最大价值。那么我们如何得到f[i][j]呢我们运用递推的思想。由于第i个物品只有选和不选两种情况当不选第i个物品时f[i][j]f[i-1][j]即取前i-1个物品且总体积小于等于j的所有取法中的最大价值当选第i个物品时我们要为第i个物品留出空间此时f[i][j]f[i-1][j-v[i]]wi即取前i-1个物品且总体积不能超过j-v[i]的取法中的最大价值再加上第i个物品的价值。因此代码如下
#includeiostream
#includecmath
using namespace std;
const int K 1010;int v[K],w[K],f[K][K];int main()
{//本来应该对f[0][0~V]进行初始化为0但由于我们开的数组是全局变量自动初始化为0因此这一步省略了。int N,V;cinNV;//一定要从下标1开始读入数据因为后面是从下标1开始遍历物品的如果从下标0开始读入会遗漏第一个物品。for(int i 1;iN;i) cinv[i]w[i];//由于i-1应该大于等于0所以从i1开始遍历。for(int i 1;iN;i){for(int j 0;jV;j){//只有在jv[i]即能放得下第i个物品的时候我们才有第二种情况。因此我们不妨直接先让f[i][j]继承f[i-1][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][V]endl;return 0;
} 那么我们如何对代码进行优化呢我们能不能让f[j]表示总体积小于等于j的取法中的最大价值呢答案是肯定的。请看代码——
#includeiostream
#includecmath
using namespace std;
const int K 1010;int v[K],w[K],f[K];int main()
{int N,V;cinNV;for(int i 1;iN;i) cinv[i]w[i];for(int i 1;iN;i)//这里省略了一行恒等式f[j] f[j]。这个式子的含义是当j小于v[i]时我们不能取第i个物品。//这里要从大到小遍历是为了避免某个物品被重复取用。如图————for(int j V;jv[i];j--)f[j] max(f[j],f[j-v[i]]w[i]);coutf[V]endl;return 0;
} 在计算f[2]时我们可以发现物品1被放进去了两次这是不被允许的。会产生这样结果的原因是j - v[i]j,那么f[j-v[i]]在该第i轮循环中已经被计算过也就是说f[j-v[i]]的真实含义是f[i][j-v[i]]它的值已经被“污染”。但是对比上一份二维数组的代码我们知道我们要的其实是f[i-1][j-v[i]]。而若倒序遍历j-v[i]j遍历到j-v[i]在j之后也就是说第i轮循环时j-v[i]还没有计算到代码会利用第i-1轮循环的值来代替这正合我们的心意。 我们还可以优化输入边输入边处理这样就不用开额外的数组了。
#includeiostream
#includecmath
using namespace std;const int K 1010;
int f[K];int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w;cinvw;for(int j V;jv;j--)f[j] max(f[j],f[j-v]w);}coutf[V]endl;
}2.完全背包问题 我们仍然首先考虑朴素算法。像上一题一样我们开一个f数组其中f[i][j]表示在前i个物品中取且总体积不大于j的取法的最大价值。那么第i个物品可以取0,1,2,3……k个。第i个物品不能无限取因为背包的容量是有限的。那么我们就有了递推式这里kv[i]V且j-kv[i]0,因为jV,我们只需要让k*v[i]j——
f[i][j] max(f[i-1][j-0*v[i]]0*w[i],f[i-1][j-1*v[i]]1*w[i],……,f[i-1][j-k*v[i]]k*w[i]);代码如下——
#includeiostream
#includecmath
using namespace std;const int K 1001;
int f[K][K];int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w;cinvw;for(int j 0;jV;j){for(int k 0;k*vj;k)f[i][j] max(f[i][j],f[i-1][j-k*v]k*w);}}coutf[N][V]endl;return 0;
}这样我们就用到了三层循环。但是这个方法在Acwing中是会爆TLE的我们能不能通过观察减少循环次数呢 因此我们的代码可以被优化为——
#includeiostream
#includecmath
using namespace std;const int K 1001;
int f[K][K];int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w;cinvw;for(int j 0;jV;j){if(jv) f[i][j] max(f[i-1][j],f[i][j-v]w);//别忘了考虑jv即放不下第i个物品的情形else f[i][j] f[i-1][j];}}coutf[N][V]endl;return 0;
}优化成一维数组如下
#includeiostream
#includecmath
using namespace std;const int K 1001;
int f[K];int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w;cinvw;for(int j v;jV;j)//这里不需要倒序遍历是因为我们要的本来就是f[i][j-v]就是在这一层被算过的.倒序反而会出错因为j-vj还没有在这一层被算过因此会调用f[i-1][j-v]这不是我们想要的。f[j] max(f[j],f[j-v]w);}coutf[V]endl;return 0;
}3.多重背包问题朴素版 #includeiostream
using namespace std;const int K 1010;
int f[K][K];int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w,s;cinvws;for(int j V;j0;j--)for(int k 0;k*vjks;k)f[i][j] max(f[i][j],f[i-1][j-k*v]k*w);}coutf[N][V]endl;return 0;
}4.多重背包问题二进制优化版 当我们尝试像3.一样对代码进行优化时我们会发现一个问题即f[i][j]不能直接由f[i][j-v]来表示。原因如下图假设总体积不大于j时所有该物品都能被放进去—— 我们会发现f[i][j-v[i]]会多出来一项导致不能完全对齐。那么为什么在完全背包问题中不会出现这种情况呢因为那里的物品时无限个的制约物品个数的是j而不是s所以可以对齐。那么我们该如何进行优化呢这里介绍二进制优化的神奇方法。它的基本思想是按照2的整数次幂将物品分为若干组每组只有取和不取两种情况。这样就转化成了一个01背包问题。那么这样的分法是否可以囊括所有可能的选择呢请看—— 如果s是一般的数不能被表示成2的幂乘的和呢 下面让我们一起来看看具体的代码实现吧
#includeiostream
#includecmath
using namespace std;
//由于log2(2000)*1000 11000我们开到15000。
const int K 15000;
//processed_v、processed_w分别表示打包后的体积和价值。
int f[K],processed_v[K],processed_w[K];
//cnt为计数器表示当前的组数。
int cnt 0;int main()
{int N,V;cinNV;for(int i 1;iN;i){int v,w,s;cinvws;int k 1;while(ks){cnt;processed_v[cnt] k*v;processed_w[cnt] k*w;s-k;k*2;}//如果有剩下也要打包if(s0){cnt;processed_v[cnt] s*v;processed_w[cnt] s*w;}}//对打包后的物品做01背包问题。for(int i 1;icnt;i)for(int j V;jprocessed_v[i];j--)f[j] max(f[j],f[j-processed_v[i]]processed_w[i]);coutf[V]endl;return 0;
}5.分组背包问题 以上就是本篇文章的全部内容啦如果你感觉有帮助请多多支持博主
