背包模型的补充与练习
采药
题目链接：采药
分析：非常明显的01背包
代码实现：
#include<iostream>
using namespace std;
int n,m;
const int N=110,M=1010;
int w[N],v[N];
int dp[M];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
for(int j=m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
Make Them Equal
题目：
除夕夜跨年打的一场cf的D题，当时现场看出来了是01背包，可惜细节上有些错误，然后自己摆烂上床休息了，要不然上大分 。
分析：通过题目给我们的信息，我们可以递推出来1转移到1000以内每个数所需的最小步骤，然后就是01背包问题了，可是这样的话会计算109次，我们可以在代码中做一个小小的优化，具体见代码。
代码实现：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef long long LL;
const int N = 1e3 + 10, M = 1e6 + 10;;
const double eps = 1e-6;
int t, a[N], b[N], c[N], n, k, cost[N], dp[M];//cost[i]表示1转移到i所需最小步骤
void init() {
cost[1] = 0;
for (int i = 1; i <= 1000; i++) {
for (int j = 1; j <= i; j++) {
int tar = i + i / j;
if (tar <= 1000) {
cost[tar] = min(cost[tar], cost[i] + 1);//保留最小的一个，刚开始我以为第一次转移到的时候值就是最小的，然后WA了一发就摆烂了，其实随意模拟几个比较小的数就知道并不一定
}
}
}
}
int main() {
memset(cost, 0x3f, sizeof cost);//初始化为很大的数
init();//初始化cost数组
cin >> t;
while (t--) {
cin >> n >> k;
int sum = 0, tot = 0;
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++) cin >> b[i], sum += cost[b[i]];//sum存储所有数需要的总步数和
for (int i = 1; i <= n; i++) cin >> c[i], tot += c[i];//tot存储总共的价值
if (k >= sum) {//如果sum<=k直接输出，然后continue，我们可以判断，当k非常大(比如说大于12000)时，就一定会在这里就直接输出tot，这样我们的时间复杂度一定不会超过1.2*10^7，2s内是稳过的
cout << tot << endl;
continue;
}
for (int i = 1; i <= n; i++) {//01背包
for (int j = k; j >= cost[b[i]]; j--) {
dp[j] = max(dp[j], dp[j - cost[b[i]]] + c[i]);
}
}
cout << dp[k] << endl;
}
return 0;
}
宠物小精灵之收服
题目链接：宠物小精灵之收服
分析：由题意我们知道，这是一个二维费用的背包问题，而且皮卡丘的血量不能降到0（否则就无法收服），我们只需要在原有的状态上加上一维，循环也加上一重，就能求出最终答案了。
代码实现：
这里直接贴上优化掉一维空间后的代码
#include<iostream>
using namespace std;
int n,m,k;
const int M=510,N=1010;
int f[N][M];//f[i][j]表示使用不超过i个精灵球，皮卡丘耗费血量不超过j-1的所有选法中捕捉的最大数量
int main(){
cin>>n>>m>>k;
for(int i=1,c,h;i<=k;i++){
cin>>c>>h;
for(int l=n;l>=c;l--){//这两重循环的先后顺序对答案没有影响
for(int j=m-1;j>=h;j--){//从m-1开始
f[l][j]=max(f[l][j],f[l-c][j-h]+1);
}
}
}
cout<<f[n][m-1]<<" ";
int ans=0;
while(f[n][ans]!=f[n][m-1]) ans++;//找到与最终答案相等时的最小耗费血量
cout<<m-ans;
return 0;
}
数字组合
题目链接：数字组合
分析：01背包的方案数问题，和01背包差不多，只需要把状态表示的含义改为方案数，转移的时候直接加上即可。
代码实现：
朴素版
#include<iostream>
using namespace std;
const int N=110,M=1e4+10;
int dp[N][M],n,tmp,m;//dp[i][j]表示考虑前i个数，组成j的方案总数
int main(){
cin>>n>>m;
dp[0][0]=1;//考虑前0个物品组成0，也算一种方案
for(int i=1;i<=n;i++){
cin>>tmp;
for(int j=0;j<=m;j++){
if(j>=tmp) dp[i][j]+=dp[i-1][j-tmp];//如果j>=tmp,说明可以选上此数字
dp[i][j]+=dp[i-1][j];//不选此数字
}
}
cout<<dp[n][m];
return 0;
}
优化一维空间，这里的思想和01背包优化掉一维空间时相似，就不再赘述
#include<iostream>
using namespace std;
const int N=110,M=1e4+10;
int dp[M],n,tmp,m;
int main(){
cin>>n>>m;
dp[0]=1;
for(int i=1;i<=n;i++){
cin>>tmp;
for(int j=m;j>=tmp;j--){
dp[j]+=dp[j-tmp];
}
}
cout<<dp[m];
return 0;
}
买书
题目链接：买书
分析：完全背包的方案数问题，同样的思考方式，把状态的表示改一改就好了。 本题相当于只有4个物品。
代码实现；
#include<iostream>
using namespace std;
const int N=1010;
int v[5]={0,10,20,50,100},n,dp[5][N];//v的第一个数设为0就是为了占个位，因为本人喜欢从1开始循环
int main(){
cin>>n;
dp[0][0]=1;
for(int i=1;i<5;i++){//考虑1~4中的4个物品
for(int j=0;j<=n;j++){//考虑体积的所有情况
for(int k=0;k*v[i]<=j;k++){//考虑能买的个数的所有情况
dp[i][j]+=dp[i-1][j-k*v[i]];//方案数直接加上
}
}
}
cout<<dp[4][n]<<endl;
return 0;
}
我们发现:对第i个物品，假设其体积为v，则有
dp[i][j]=dp[i-1][j]+dp[i-1][j-v]+dp[i-1][j-2*v]+...dp[i-1][j-k*v](k*v<=j&&(k+1)*v>j)
dp[i][j-v]=dp[i-1][j-v]+dp[i-1][j-2*v]+...dp[i-1][j-k*v](k*v<=j&&(k+1)*v>j)
因此，我们得到dp[i][j]=dp[i-1][j]+dp[i][j-v]因此我们又可以优化掉一维了！
#include<iostream>
using namespace std;
const int N=1010;
int v[5]={0,10,20,50,100},n,dp[N];
int main(){
cin>>n;
dp[0]=1;
for(int i=1;i<5;i++){
for(int j=v[i];j<=n;j++){
dp[j]+=dp[j-v[i]];
}
}
cout<<dp[n]<<endl;
return 0;
}
货币系统
题目链接：货币系统
分析：我们要找到货币系统(m,b)满足与货币系统(n,a)等价并且m尽可能的小，我们可以先假设(m,b)与(n,a)完全相同，然后寻找(m,b)中有没有可以去掉的货币，例如(n,a)中货币有2，3，5，9，13，那么显然(m,b)中的5，9，13都可以去掉，我们发现最小的货币肯定不会被去掉，因此我们从小到大考虑每一个货币，通过这个货币转移状态，按完全背包的方案数问题求组成每个数字的方案数（只需求到最大的货币），如果组成当前的货币的方案数为0，就进行转移，否则就不用转移。
代码实现：
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=110,M=25010;
int dp[M],a[N];//dp[i]表示组成i的方案数
int main(){
int T;
cin>>T;
while(T--){
memset(dp,0,sizeof dp);
dp[0]=1;
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);//排序
int res=0;
for(int i=1;i<=n;i++){//从小到大考虑每个数
if(!dp[a[i]]){//如果组成这个数的方案数为0，就res++，并更新这个数到最大的数之间所有数的组成方案数（完全背包的方案数问题）
res++;
for(int j=a[i];j<=a[n];j++)
dp[j]+=dp[j-a[i]];
}
//如果这个数的组成方案数不为0，说明前面的数就能组成它了，也就不需要它了
}
cout<<res<<endl;
}
return 0;
}
NOIP2018提高组的题，还是有点意思的
多重背包问题3
题目链接：多重背包问题3
终于来了，这道题快把我折磨死了 。这道题在多重背包问题2的基础上又增大了v的范围和s的范围，这样我们就不能用二进制优化过这道题了。这时候我们再观察状态转移方程。用dp[i][j]表示只考虑前i个物品，总体积不超过j的所有选法中价值的最大值，我们由上次的文章可以知道(v为第i个物品二的体积，w为第i个物品的价值，s为个数)：
对第i个物品，我们设j%v=r，在数轴上表上所有转移状态需要用到的j的值，从右往左依次为j,j-v,j-2*v…j-k *v
我们发现，如果我们忽略偏移量（即每个数后面加的w的若干倍），我们求f[i][j]时，只用考虑数轴上最后s个数的最大值就可以了，这就是一个滑动窗口了（如果滑动窗口内的数不足s个，就算这么多里面的最大值），接下来我们考虑如何忽略偏移量，我们从最后一个点看起，我们得到：
f[i][r]=f[i-1][r]
f[i][r+v]=max(f[i-1][r]+w,f[i-1][r+v])
f[i][r+2*v]=max(f[i-1][r]+2*w,f[i-1][r+v]+w,f[i-1][r+2*v])
......
我们把等号右边括号中的w提出来，则有：
f[i][r]=f[i-1][r]
f[i][r+v]=max(f[i-1][r],f[i-1][r+v]-w)+w
f[i][r+2*v]=max(f[i-1][r],f[i-1][r+v]-w,f[i-1][r+2*v]-2*w)+2*w
......
我们发现，f[i][r+k*v]入队时只要减去一个k *w的偏移量就行了，然后f[i][r+k *v]取完最大之后加上k *w就可以了。而r的取值有0~v-1这v种情况，所以也需要一个循环，最后就是代码环节：
因为我们考虑到第i个物品时只会用到第i-1个物品的状态，因此我们就开一个pre数组记录上一个物品的状态。（看着公式更容易看懂）
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e4+10;
int dp[N],pre[N],q[N];//q队列中存储的是体积，pre数组存储前i-1个物品对应的数据
int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){//枚举n个物品
memcpy(pre,dp,sizeof dp);
int v,w,s;
cin>>v>>w>>s;
for(int j=0;j<v;j++){//枚举余数
int head=0,tail=-1;//数组模拟队列
for(int k=j;k<=m;k+=v){//枚举所有要更新的体积
if(head<=tail&&k-s*v>q[head])//k-s*v>队头的体积时代表已经超出滑动窗口的大小了
++head;
while(head<=tail&&pre[q[tail]]-q[tail]/v*w<=pre[k]-k/v*w) --tail;//如果队尾体积对应的价值（这里的值表示减去偏移量后的值）小于等于要进来的体积对应的价值并且队列不空，就弹出队尾
q[++tail]=k;//新体积入队
dp[k]=pre[q[head]]+(k-q[head])/v*w;//更新答案，这里的答案是去掉偏移量后的答案，因为q中的体积肯定也都是r+k*v的样式，因此可以这么写
}
}
}
cout<<dp[m]<<endl;
return 0;
}
顺带一题，这个算法的时间复杂度是O(n*v)，因为我们可以知道，j和k的两重循环全部加起来后，每个体积也只会被枚举一次。
混合背包问题
题目链接：混合背包问题
分析：也算是较有意思的一题了，对可以无限使用的物品就用完全背包，否则就用多重背包，另外数据范围较大，因此用二进制优化完全背包。
代码实现：
#include<iostream>
using namespace std;
int n,m;
const int N=1010;
int dp[N];
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
int v,w,s;
cin>>v>>w>>s;
if(s==0){
for(int j=v;j<=m;j++){//完全背包从小到大枚举
dp[j]=max(dp[j],dp[j-v]+w);
}
}
else{
if(s==-1) s=1;//如果s==-1，说明就1个
for(int k=1;k<=s;k*=2){//二进制优化成01背包
for(int j=m;j>=k*v;j--){
dp[j]=max(dp[j],dp[j-k*v]+k*w);
}
s-=k;
}
if(s){//如果还剩
for(int j=m;j>=s*v;j--){
dp[j]=max(dp[j],dp[j-s*v]+s*w);
}
}
}
}
cout<<dp[m]<<endl;
return 0;
}
二维费用的背包问题
题目链接：二维费用的背包问题
分析：然而我上面先写了应用题后才碰到这个模板题。。。和01背包差不多，只不过是把状态改为二维。
代码实现：
#include<iostream>
using namespace std;
const int M=110;
int dp[M][M];
int main(){
int n,v,m;
cin>>n>>v>>m;
for(int i=0;i<n;i++){
int vol,wei,val;
cin>>vol>>wei>>val;
for(int j=m;j>=wei;j--){
for(int k=v;k>=vol;k--){
dp[j][k]=max(dp[j][k],dp[j-wei][k-vol]+val);
}
}
}
cout<<dp[m][v]<<endl;
return 0;
}
潜水员
题目链接：潜水员
分析：比较有意思的一题，可以理解为二位费用的01背包问题求最小价值，只需稍改代码。
代码实现：
#include<iostream>
#include<cstring>
using namespace std;
const int N=22,M=80;
int dp[N][M];//dp[i][j]表示要满足i氧气和j氮气所需的最小重量
int main(){
int n,m,k;
cin>>n>>m>>k;
memset(dp,0x3f,sizeof dp);//初始化为很大的数
dp[0][0]=0;//要0氧气和0氮气需要的重量
while(k--){
int v1,v2,w;
cin>>v1>>v2>>w;
for(int i=n;i>=0;i--){
for(int j=m;j>=0;j--){
dp[i][j]=min(dp[i][j],dp[max(0,i-v1)][max(0,j-v2)]+w);//状态转移，注意如果超过了所需，也是满足
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
背包问题求方案数
题目链接：背包问题求方案数
分析：我们只需把f[i]改为体积恰好为i时的最大价值，再开一个新数组记录方案数即可，如果直接看优化成一维的方案看不懂，最好先自己写写二维的，再转化成一维的。
代码实现：
#include<iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int dp[N],ans[N];//dp[j]定义为体积恰好为j时的价值最大值，ans[i]表示体积恰好为i时的方案数
int a[N],b[N];
int main(){
int n,v;
cin>>n>>v;
for(int i=0;i<n;i++) cin>>a[i]>>b[i];
ans[0]=1;//ans[0]设为1，因为什么都不选也是一种方案
for(int i=0;i<n;i++){//考虑n个物品
for(int j=v;j>=a[i];j--){//01背包优化掉一维后的写法
int maxt=max(dp[j],dp[j-a[i]]+b[i]);//先把最大值记录一下
int cnt=0;//cnt记录方案数
if(maxt==dp[j]) cnt+=ans[j];//如果能从dp[j]转移而来，加上方案数
if(maxt==dp[j-a[i]]+b[i]) cnt+=ans[j-a[i]];//如果从dp[j-a[i]]+b[i]能转移过来，加上方案数
ans[j]=cnt%mod;//方案数%mod后赋值给ans[j]
dp[j]=maxt;//maxt赋值给dp[j]
}
}
int res=0;
for(int i=1;i<=v;i++){//遍历一遍找答案，因为这里是恰好，所以要遍历一遍找答案
res=max(res,dp[i]);
}
int cnt=0;
for(int i=0;i<=v;i++){//这里要从0开始，否则如果出现一个物品都选不了的情况，答案就会出错
if(res==dp[i])//如果和答案一样
cnt=(cnt+ans[i])%mod;//方案数累加起来
}
cout<<cnt<<endl;
return 0;
}
背包问题求具体方案
题目链接：背包问题求具体方案
分析：01背包问题，不优化空间了，算完后直接递推出答案，由于答案要求我们输出字典序最小的答案，我们可以从第n个物品到第1个物品顺次考虑，找答案的时候再从第一个物品开始，这样我们就会优先选择前面的物品。
代码实现：
#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int w[N],v[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=n;i>0;i--){//从最后一个到第一个物品01背包
for(int j=0;j<=m;j++){
f[i][j]=f[i+1][j];//注意这里以及下面都要变成i+1，因为第i个物品的状态是从第i+1个物品转移而来的
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
int j=m;
for(int i=1;i<=n;i++){//从第一个物品开始
if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]){//如果能转移，就选上
cout<<i<<" ";
j-=v[i];//剩余总体积减去v[i]
}
}
return 0;
}
机器分配
题目链接：机器分配
分析：就是求多重背包的具体方案，我突然又想起了那句话：时间复杂度越高的算法往往越全能。我们直接求出最终答案，然后通过答案往前递推出方案即可。
代码实现：
#include<iostream>
using namespace std;
const int N=11,M=16;
int w[N][M],f[N][M],n,m,ans[N];//w[i][j]存储第i个公司用j台设备的盈利，f[i][j]表示考虑前i家公司和j台设备的最大盈利，ans[i]表示i公司所用的设备数
//本题中不能再优化空间了，否则没法根据答案推出各个公司使用的设备数
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
for(int i=1;i<=n;i++)//考虑前i家公司
for(int j=0;j<=m;j++)//总数不超过j
for(int k=0;k<=j;k++)//使用的设备数
f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
cout<<f[n][m]<<endl;
int j=m;//j表示剩余的总体积，初始值为m
for(int i=n;i;i--)//从后往前枚举每家公司
for(int k=0;j<=j;k++)
if(f[i][j]==f[i-1][j-k]+w[i][k]){//如果f[i][j]是由f[i-1][j-k]+w[i][k]转移来的
j-=k;//用掉了k体积
ans[i]=k;//记录答案
break;//终止循环
}
for(int i=1;i<=n;i++) cout<<i<<" "<<ans[i]<<endl;
return 0;
}
有依赖的背包问题
题目链接：有依赖的背包问题
分析：看到这题我想起了没有上司的舞会，感觉差不多，这又是个背包问题，我们需要对状态表示稍作修改，另外，状态转移的时候我们很难枚举子树的所有选法，枚举体积不失为一种好策略。
代码实现：
#include<iostream>
using namespace std;
int n,m;
const int N=110;
int v[N],dp[N][N],w[N],p,root,e[N],ne[N],idx=1,h[N];//dp[i][j]表示在以i为根节点的子树、体积不超过j的选法中的最大价值
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u){//在这里如果我们枚举子树的选法，就会有非常多的情况(2^k级别)，因此这里我们换成枚举体积
for(int i=h[u];i;i=ne[i]){//遍历所有子结点，整个循环相当于一个01背包，每个子树都是一种物品，但可以选择任意可行的体积
int t=e[i];
dfs(t);//递归子树
for(int j=m-v[u];j>=0;j--){//因为必须选中根节点，子树可用体积只剩m-v[u]
for(int k=0;k<=j;k++){//枚举当前子树体积
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[t][k]);
}
}
}
//更新完子树，更新加上根节点的选法
for(int i=m;i>=v[u];i--) dp[u][i]=dp[u][i-v[u]]+w[u];//对于可以选中根结点的体积，更新答案
for(int i=0;i<v[u];i++) dp[u][i]=0;//否则就是0
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>p;
if(p==-1) root=i;//记录根节点
else{
add(p,i);//添加一条父亲指向儿子的边
}
}
dfs(root);
cout<<dp[root][m]<<endl;
return 0;
}
金明的预算方案
题目链接：金明的预算方案
分析：一道有依赖的背包问题，不过这道题用01背包就能解决了。
代码实现：
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N=32010,M=65;
PII mas[M];//存储主件
vector<PII> ser[M];//ser[i]存储的是i的所有附件
int dp[N];//01背包的状态表示
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int v,p,q;
cin>>v>>p>>q;
if(!q) mas[i]={v,v*p};//如果不是附件
else ser[q].push_back({v,v*p});//如果是附件
}
for(int i=1;i<=m;i++){//对每个主附件对做01背包
for(int u=n;u>=0;u--){//体积从大到小
for(int j=0;j<1<<ser[i].size();j++){//如果不是主件，这里会直接跳过，否则进入（2进制优化表示每个附件选与不选）
int v=mas[i].first,w=mas[i].second;//加上主件的v和w，因为主件必选
for(int k=0;k<ser[i].size();k++){//k位2进制数分别表示每个附件选与不选
if(j>>k&1){//如果选，就加上
v+=ser[i][k].first,w+=ser[i][k].second;
}
}
if(u>=v) dp[u]=max(dp[u],dp[u-v]+w);//能转移，就转移
}
}
}
cout<<dp[n]<<endl;
return 0;
}
能量石
题目链接：能量石
分析：看完题目描述，我们可以类似于国王游戏那题，得出一个贪心的结论，对能量石a，b，它们俩的参数分别是s1,e1,l1和s2,e2,l2，如果先吃a，则获取能量为e1+e2-l2*s1，反之获取能量为e+e2-l1*s2，我们得到，若l1*s2>l2*s1，则先吃a更赚，然后其实这就是一个01背包问题，一个石头可能有很大的价值但却占用很多空间，我们用01背包来权衡选与不选，只不过在加上它的价值时我们需要减去它已损失的价值并保证为非负数，另外，在寻找答案时答案不一定是最后一个时间对应的状态，因为它转移的时候可能有的能量石能量已经耗尽了，因此我们可以遍历一遍所有体积，找出最大的价值就是答案。
代码实现：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, M = 10010;
int n;
struct Stone{
int s, e, l;
}stones[N];
bool cmp(Stone a, Stone b){
return a.s * b.l < b.s * a.l;
}
int f[N][M];
int main(){
int T;
cin >> T;
for (int C = 1; C <= T; C ++ ){
cin >> n;
int m = 0;//记录总时间
for (int i = 1; i <= n; i ++ ){
int s, e, l;
cin >> s >> e >> l;
stones[i] = {s, e, l};
m += s;//累加上去，时间最长的情况下所有石头都不流失能量，因此我们都加上
}
sort(stones + 1, stones + 1 + n, cmp);//按规定的函数排序，保证流失的能量最少
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ ){
f[i][j] = f[i - 1][j];
if (j >= stones[i].s){//能吃的话就试着转移
int s = stones[i].s, e = stones[i].e, l = stones[i].l;
f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
}
}
int res = 0;
for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]);//找出最大的作为答案
printf("Case #%d: %d\n", C, res);
}
return 0;
}
扫一扫
887
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
