Part 4.2 背包动态规划

->背包模型模板(0/1,分组，完全，多重)<-

[NOIP2018 提高组] 货币系统

题目背景

NOIP2018 提高组 D1T2

题目描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 $n$、面额数组为 $a[\mathrm{1..}n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i]\times t[i]$ 的和为 $x$。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3$, $a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

输入格式

输入文件的第一行包含一个整数 $T$，表示数据的组数。

接下来按照如下格式分别给出 $T$ 组数据。 每组数据的第一行包含一个正整数 $n$。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$。

样例 #1

样例输入 #1

2 
4 
3 19 10 6 
5 
11 29 13 19 17

样例输出 #1

2   
5

提示

在第一组数据中，货币系统 $(2,[3,10])$ 和给出的货币系统 $(n,a)$ 等价，并可以验证不存在 $m<2$ 的等价的货币系统，因此答案为 $2$。 在第二组数据中，可以验证不存在 $m<n$ 的等价的货币系统，因此答案为 $5$。

【数据范围与约定】

对于 $100\%$ 的数据，满足 $1\le T\le 20,n,a[i]\ge 1$。

解题思路

vis[i]=(vis[i-money[j]]>1)?2:0
vis[i]的值为0，说明不可得到值为i的数，1表示本来就存在值为i的面值，2表示可以拼凑得到值为i的面值，2可以覆盖1，从而达成减少种类的目的。

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t;
#define MAX_N 100
#define MAX_A 25000
int money[MAX_N+5];
int vis[MAX_A+5];
void solve()
{memset(vis,0,sizeof vis);int n;cin>>n;for(int i=1;i<=n;i++){cin>>money[i];vis[money[i]]=1;}sort(money+1,money+1+n);for(int i=1;i<=money[n];i++){for(int j=1;j<n;j++){if(money[j]>=i)break;if(!vis[i-money[j]])continue;vis[i]=2;}}int ans=0;for(int i=1;i<=money[n];i++)if(vis[i]==1)ans++;cout<<ans<<endl;
}
int main()
{cin>>t;while(t--)solve();return 0;
} 

通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

10

提示

$0\le m\le 1000$，$1\le n\le 1000$，$1\le k\le 100$，$a_i,b_i,c_i$ 在 int 范围内。

解题思路

dp[i][j]:前i个分组在容量为觉得情况下的最大价值
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w)

代码实现1

#include<iostream>
#include<algorithm> 
using namespace std;
#define MAX_N 1000
struct Data{int a,b,c;
}item[MAX_N+5];
int dp[MAX_N+5][MAX_N+5];//此处为前i个物品，容量为j的情况下的最大价值
bool cmp(Data a,Data b)
{return a.c<b.c;
}
int main()
{int m,n;cin>>m>>n;for(int i=1;i<=n;i++){cin>>item[i].a>>item[i].b>>item[i].c;}sort(item+1,item+n+1,cmp);int cnt=1;for(int i=1;i<=n;i++){if(item[i].c==item[i-1].c)cnt++;else cnt=1;for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(j>=item[i].a)dp[i][j]=max(dp[i][j],dp[i-cnt][j-item[i].a]+item[i].b);}}cout<<dp[n][m];return 0;
}

代码实现2

#include<bits/stdc++.h>
using namespace std;
int v,n,t;
int x;
int g[205][205];
int i,j,k;
int w[10001],z[10001];
int b[10001];
int dp[10001];
int main(){cin>>v>>n;for(i=1;i<=n;i++){cin>>w[i]>>z[i]>>x;t=max(t,x);b[x]++;g[x][b[x]]=i;}for(i=1;i<=t;i++){for(j=v;j>=0;j--){for(k=1;k<=b[i];k++){if(j>=w[g[i][k]]){dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);}}}}cout<<dp[v];return 0;
}

[USACO09MAR] Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的 $N$ 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 $i$ 头奶牛的能力为 $R_i$。飞盘队的队员数量不能少于 $1$、大于 $N$。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信，他的幸运数字是 $F$，所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 $10^8$ 取模的值。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $F$。

第二行到 $N+1$ 行：第 $i+1$ 行有一个整数 $R_i$，表示第 $i$ 头奶牛的能力。

输出格式

第一行：单个整数，表示方案数对 $10^8$ 取模的值。

样例 #1

样例输入 #1

4 5 
1 
2 
8 
2

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le N\le 2000$，$1\le F\le 1000$，$1\le R_i\le 10^5$。

解题思路

状态定义：dp[i][j]:前i头牛对f取模为j的方案总数
转移方程：dp[i][j]=dp[i-1][j]+dp[i-1][(j-val[i]%f+f)%f]
特别注意，对于每一个val[i]%f都要在dp[i][val[i]%f]的位置上加上一个1

代码实现

#include<iostream>
using namespace std;
#define MAX_N 2000
#define MAX_F 1000
#define MOD 100000000
int dp[2][MAX_F+5];
int val[MAX_N+5];
int n,f;
int main()
{cin>>n>>f;for(int i=1;i<=n;i++){cin>>val[i];val[i]%=f;}int now=0;for(int i=1;i<=n;i++){for(int j=0;j<f;j++){dp[now][j]=(dp[now^1][j]+dp[now^1][(j-val[i]+f)%f])%MOD;}dp[now][val[i]]+=1;now^=1;}cout<<dp[now^1][0];return 0;} 

垃圾陷阱

题目描述

卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方，它的深度为 $D$（$2\le D\le 100$）英尺。

卡门想把垃圾堆起来，等到堆得与井深同样高或比井深更高（即，垃圾高度总和 $\ge D$）时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间 $t$（$1\le t\le 1000$），以及每个垃圾堆放的高度 $h$（$1\le h\le 25$）和吃进该垃圾能增加维持生命的时间 $f$（$1\le f\le 30$），要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续 $10$ 小时的能量，如果卡门 $10$ 小时内（不含 $10$ 小时，维持生命的时间同）没有进食，卡门就将饿死。特别地，若体力值为 $0$ 时吃下垃圾或逃出井外也不会饿死。

输入格式

第一行为两个整数，$D$ 和 $G$（$1\le G\le 100$），$G$ 为被投入井的垃圾的数量。

第二到第 $G+1$ 行每行包括三个整数：$T$（$1\le T\le 1000$），表示垃圾被投进井中的时间；$F$（$1\le F\le 30$），表示该垃圾能维持卡门生命的时间；和 $H$（$1\le H\le 25$），该垃圾能垫高的高度。

输出格式

如果卡门可以爬出陷阱，输出一个整数，表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

样例 #1

样例输入 #1

20 4
5 4 9
9 3 2
12 6 10
13 1 1

样例输出 #1

13

提示

【样例说明】

卡门堆放她收到的第一个垃圾：$\mathrm{height}=9$；

卡门吃掉她收到的第 $2$ 个垃圾，使她的生命从 $10$ 小时延伸到 $13$ 小时；

卡门堆放第 $3$ 个垃圾，$\mathrm{height}=19$；

卡门堆放第 $4$ 个垃圾，$\mathrm{height}=20$。

解题思路

状态定义：dp[i][j]表示前i个垃圾在能量为j的情况下的最大高度
转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-f]+h)

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_D 100
#define MAX_G 100
int d,g;
struct Data{int t,f,h;
}rubbish[MAX_G+5];
int dp[MAX_G+5][3010];
int vis[MAX_G+5][3010];
bool cmp(Data a,Data b)
{return a.t<b.t;
}
int main()
{cin>>d>>g;int max_t=0,sum_f=10;for(int i=1;i<=g;i++){cin>>rubbish[i].t>>rubbish[i].f>>rubbish[i].h;max_t=max(max_t,rubbish[i].t);sum_f+=rubbish[i].f;}sort(rubbish+1,rubbish+1+g,cmp);if(rubbish[1].t<=10){dp[1][10]=rubbish[1].h;if(rubbish[1].t!=10)vis[1][10]=1;vis[1][10+rubbish[1].f]=1;if(rubbish[1].h>=d){cout<<rubbish[1].t;return 0;}}for(int i=2;i<=g;i++){for(int j=10;j<=sum_f;j++){if(j<rubbish[i].t)continue;if((j-rubbish[i].f)>=rubbish[i].t&&vis[i-1][j-rubbish[i].f])//可以由dp[i-1][j-f]转移说明 j-f本身就要大于当前时间 dp[i][j]=dp[i-1][j-rubbish[i].f],vis[i][j]=1;if(vis[i-1][j])dp[i][j]=max(dp[i][j],dp[i-1][j]+rubbish[i].h),vis[i][j]=1;if(dp[i][j]>=d){cout<<rubbish[i].t;return 0;}}}int last=10;for(int i=1;i<=g;i++){if(last>=rubbish[i].t)last+=rubbish[i].f;else{cout<<last;return 0;}}cout<<last;return 0;} 

[BJOI2019] 排兵布阵

题目描述

小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。

如果一名玩家向第 $i$ 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。

现在小 C 即将和其他 $s$ 名玩家两两对战，这 $s$ 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 $s$ 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

输入格式

输入第一行包含三个正整数 $s,n,m$，分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。
接下来 $s$ 行，每行 $n$ 个非负整数，表示一名玩家的策略，其中第 $i$ 个数 $a_i$ 表示这名玩家向第 $i$ 座城堡派遣的士兵数。

输出格式

输出一行一个非负整数，表示小 C 获得的最大得分。

样例 #1

样例输入 #1

1 3 10
2 2 6

样例输出 #1

3

样例 #2

样例输入 #2

2 3 10
2 2 6
0 0 0

样例输出 #2

8

提示

样例1解释：
小 C 的最佳策略为向第 $1$ 座城堡和第 $2$ 座城堡各派遣 $5$ 名士兵。

样例2解释：
小 C 的最佳策略之一为向第 $1$ 座城堡派遣 $2$ 名士兵，向第 $2$ 座城堡派遣 $5$ 名士兵，向第 $3$ 座城堡派遣 $1$ 名士兵。

数据范围：
对于 $10\%$ 的数据： $s=1,n\le 3,m\le 10$
对于 $20\%$ 的数据： $s=1,n\le 10,m\le 100$
对于 $40\%$ 的数据： $n\le 10,m\le 100$
对于另外 $20\%$ 的数据： $s=1$
对于 $100\%$ 的数据：
$1\le s\le 100$
$1\le n\le 100$
$1\le m\le 20000$
对于每名玩家 $a_i\ge 0$，$\sum _{i=1}^n{a}_i\le m$

解题思路

状态定义：dp[i][j]表示前i个城堡派遣j个士兵的最大得分
转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-n]+i*k) （n表示士兵人数，具体值可变，k表示可占领的城堡得数量，n和k的对应关系单独处理）

代码实现

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX_S 100
#define MAX_N 100
#define MAX_M 20000
int bing[MAX_S+5][MAX_N+5];
int dp[MAX_N+5][MAX_M+5];
vector<pair<int,int>>g[MAX_N+5];
int s,n,m;
int main()
{cin>>s>>n>>m;for(int i=1;i<=s;i++){for(int j=1;j<=n;j++){cin>>bing[j][i];}}for(int i=1;i<=n;i++)sort(bing[i]+1,bing[i]+1+s);for(int i=1;i<=n;i++){for(int j=1;j<=s;j++){if(bing[i][j]==bing[i][j+1])continue;if(bing[i][j]*2>m)break;g[i].push_back(make_pair(bing[i][j]*2+1,j));}if(bing[i][s]==0)g[i].push_back(make_pair(1,s));}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];for(auto k:g[i])if(j>=k.first)dp[i][j]=max(dp[i][j],dp[i-1][j-k.first]+i*k.second);}}cout<<dp[n][m];return 0;
}

总结：背包问题的一般形式为在若干个物品中按照一定的逻辑选择若干个，或者对于每一个物品选择其某一个属性（t4），或者对于某一个物品使用多大的代价选择其多大的部分（t5）等等，以求最后效益最大。