XCPC第九站———背包问题！

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个物品的价值。因此代码如下：

#include<iostream>
#include<cmath>
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;cin>>N>>V;//一定要从下标1开始读入数据，因为后面是从下标1开始遍历物品的，如果从下标0开始读入，会遗漏第一个物品。for(int i = 1;i<=N;i++)  cin>>v[i]>>w[i];//由于i-1应该大于等于0，所以从i=1开始遍历。for(int i = 1;i<=N;i++){for(int j = 0;j<=V;j++){//只有在j>=v[i]，即能放得下第i个物品的时候我们才有第二种情况。因此我们不妨直接先让f[i][j]继承f[i-1][j]，然后再在满足条件时取两者中的最大值即可。f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[N][V]<<endl;return 0;
}

        那么我们如何对代码进行优化呢？我们能不能让f[j]表示总体积小于等于j的取法中的最大价值呢？答案是肯定的。请看代码——

#include<iostream>
#include<cmath>
using namespace std;
const int K = 1010;int v[K],w[K],f[K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++)  cin>>v[i]>>w[i];for(int i = 1;i<=N;i++)//这里省略了一行恒等式：f[j] = f[j]。这个式子的含义是，当j小于v[i]时，我们不能取第i个物品。//这里要从大到小遍历，是为了避免某个物品被重复取用。如图————for(int j = V;j>=v[i];j--)f[j] = max(f[j],f[j-v[i]]+w[i]);cout<<f[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轮循环的值来代替，这正合我们的心意。
        我们还可以优化输入，边输入边处理，这样就不用开额外的数组了。

#include<iostream>
#include<cmath>
using namespace std;const int K = 1010;
int f[K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w;cin>>v>>w;for(int j = V;j>=v;j--)f[j] = max(f[j],f[j-v]+w);}cout<<f[V]<<endl;
}

2.完全背包问题

        我们仍然首先考虑朴素算法。像上一题一样，我们开一个f数组，其中f[i][j]表示在前i个物品中取且总体积不大于j的取法的最大价值。那么第i个物品可以取0,1,2,3……k个。第i个物品不能无限取，因为背包的容量是有限的。那么我们就有了递推式（这里kv[i]<=V且j-kv[i]>=0,因为j<=V,我们只需要让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]);

代码如下——

#include<iostream>
#include<cmath>
using namespace std;const int K = 1001;
int f[K][K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w;cin>>v>>w;for(int j = 0;j<=V;j++){for(int k = 0;k*v<=j;k++)f[i][j] = max(f[i][j],f[i-1][j-k*v]+k*w);}}cout<<f[N][V]<<endl;return 0;
}

        这样我们就用到了三层循环。但是这个方法在Acwing中是会爆TLE的，我们能不能通过观察减少循环次数呢？

        因此我们的代码可以被优化为——

#include<iostream>
#include<cmath>
using namespace std;const int K = 1001;
int f[K][K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w;cin>>v>>w;for(int j = 0;j<=V;j++){if(j>=v)    f[i][j] = max(f[i-1][j],f[i][j-v]+w);//别忘了考虑j<v，即放不下第i个物品的情形else    f[i][j] = f[i-1][j];}}cout<<f[N][V]<<endl;return 0;
}

        优化成一维数组如下：

#include<iostream>
#include<cmath>
using namespace std;const int K = 1001;
int f[K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w;cin>>v>>w;for(int j = v;j<=V;j++)//这里不需要倒序遍历，是因为我们要的本来就是f[i][j-v]，就是在这一层被算过的.倒序反而会出错，因为j-v<j还没有在这一层被算过，因此会调用f[i-1][j-v]，这不是我们想要的。f[j] = max(f[j],f[j-v]+w);}cout<<f[V]<<endl;return 0;
}

3.多重背包问题（朴素版）

#include<iostream>
using namespace std;const int K = 1010;
int f[K][K];int main()
{int N,V;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w,s;cin>>v>>w>>s;for(int j = V;j>=0;j--)for(int k = 0;k*v<=j&&k<=s;k++)f[i][j] = max(f[i][j],f[i-1][j-k*v]+k*w);}cout<<f[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的幂乘的和）呢？

        下面让我们一起来看看具体的代码实现吧！

#include<iostream>
#include<cmath>
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;cin>>N>>V;for(int i = 1;i<=N;i++){int v,w,s;cin>>v>>w>>s;int k = 1;while(k<=s){cnt++;processed_v[cnt] = k*v;processed_w[cnt] = k*w;s-=k;k*=2;}//如果有剩下，也要打包if(s>0){cnt++;processed_v[cnt] = s*v;processed_w[cnt] = s*w;}}//对打包后的物品做01背包问题。for(int i = 1;i<=cnt;i++)for(int j = V;j>=processed_v[i];j--)f[j] = max(f[j],f[j-processed_v[i]]+processed_w[i]);cout<<f[V]<<endl;return 0;
}

5.分组背包问题

以上就是本篇文章的全部内容啦！如果你感觉有帮助，请多多支持博主！