玉林市网站开发公司,温州网站建设制作,wordpress批量导入txt,网站飘落怎么做-背包模型模板(0/1,分组#xff0c;完全#xff0c;多重)-
[NOIP2018 提高组] 货币系统
题目背景
NOIP2018 提高组 D1T2
题目描述
在网友的国度中共有 n n n 种不同面额的货币#xff0c;第 i i i 种货币的面额为 a [ i ] a[i] a[i]#xff0c;你可以假设每… -背包模型模板(0/1,分组完全多重)-
[NOIP2018 提高组] 货币系统
题目背景
NOIP2018 提高组 D1T2
题目描述
在网友的国度中共有 n n n 种不同面额的货币第 i i i 种货币的面额为 a [ i ] a[i] a[i]你可以假设每一种货币都有无穷多张。为了方便我们把货币种数为 n n n、面额数组为 a [ 1.. n ] a[1..n] a[1..n] 的货币系统记作 ( n , a ) (n,a) (n,a)。
在一个完善的货币系统中每一个非负整数的金额 x x x 都应该可以被表示出即对每一个非负整数 x x x都存在 n n n 个非负整数 t [ i ] t[i] t[i] 满足 a [ i ] × t [ i ] a[i] \times t[i] a[i]×t[i] 的和为 x x x。然而 在网友的国度中货币系统可能是不完善的即可能存在金额 x x x 不能被该货币系统表示出。例如在货币系统 n 3 n3 n3, a [ 2 , 5 , 9 ] a[2,5,9] a[2,5,9] 中金额 1 , 3 1,3 1,3 就无法被表示出来。
两个货币系统 ( n , a ) (n,a) (n,a) 和 ( m , b ) (m,b) (m,b) 是等价的当且仅当对于任意非负整数 x x x它要么均可以被两个货币系统表出要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 ( m , b ) (m,b) (m,b)满足 ( m , b ) (m,b) (m,b) 与原来的货币系统 ( n , a ) (n,a) (n,a) 等价且 m m m 尽可能的小。他们希望你来协助完成这个艰巨的任务找到最小的 m m m。
输入格式
输入文件的第一行包含一个整数 T T T表示数据的组数。
接下来按照如下格式分别给出 T T T 组数据。 每组数据的第一行包含一个正整数 n n n。接下来一行包含 n n n 个由空格隔开的正整数 a [ i ] a[i] a[i]。
输出格式
输出文件共有 T T T 行对于每组数据输出一行一个正整数表示所有与 ( n , a ) (n,a) (n,a) 等价的货币系统 ( m , b ) (m,b) (m,b) 中最小的 m m m。
样例 #1
样例输入 #1
2
4
3 19 10 6
5
11 29 13 19 17样例输出 #1
2
5提示
在第一组数据中货币系统 ( 2 , [ 3 , 10 ] ) (2, [3,10]) (2,[3,10]) 和给出的货币系统 ( n , a ) (n, a) (n,a) 等价并可以验证不存在 m 2 m 2 m2 的等价的货币系统因此答案为 2 2 2。 在第二组数据中可以验证不存在 m n m n mn 的等价的货币系统因此答案为 5 5 5。
【数据范围与约定】 对于 100 % 100\% 100% 的数据满足 1 ≤ T ≤ 20 , n , a [ i ] ≥ 1 1 ≤ T ≤ 20, n,a[i] ≥ 1 1≤T≤20,n,a[i]≥1。
解题思路
vis[i](vis[i-money[j]]1)?2:0 vis[i]的值为0说明不可得到值为i的数1表示本来就存在值为i的面值2表示可以拼凑得到值为i的面值2可以覆盖1从而达成减少种类的目的。
代码实现
#includeiostream
#includealgorithm
#includecstring
using namespace std;
int t;
#define MAX_N 100
#define MAX_A 25000
int money[MAX_N5];
int vis[MAX_A5];
void solve()
{memset(vis,0,sizeof vis);int n;cinn;for(int i1;in;i){cinmoney[i];vis[money[i]]1;}sort(money1,money1n);for(int i1;imoney[n];i){for(int j1;jn;j){if(money[j]i)break;if(!vis[i-money[j]])continue;vis[i]2;}}int ans0;for(int i1;imoney[n];i)if(vis[i]1)ans;coutansendl;
}
int main()
{cint;while(t--)solve();return 0;
}
通天之分组背包
题目背景
直达通天路·小 A 历险记第二篇
题目描述
自 01 01 01 背包问世之后小 A 对此深感兴趣。一天小 A 去远游却发现他的背包不同于 01 01 01 背包他的物品大致可分为 k k k 组每组中的物品相互冲突现在他想知道最大的利用价值是多少。
输入格式
两个数 m , n m,n m,n表示一共有 n n n 件物品总重量为 m m m。
接下来 n n n 行每行 3 3 3 个数 a i , b i , c i a_i,b_i,c_i ai,bi,ci表示物品的重量利用价值所属组数。
输出格式
一个数最大的利用价值。
样例 #1
样例输入 #1
45 3
10 10 1
10 5 1
50 400 2样例输出 #1
10提示 0 ≤ m ≤ 1000 0 \leq m \leq 1000 0≤m≤1000 1 ≤ n ≤ 1000 1 \leq n \leq 1000 1≤n≤1000 1 ≤ k ≤ 100 1\leq k\leq 100 1≤k≤100 a i , b i , c i a_i, b_i, c_i ai,bi,ci 在 int 范围内。
解题思路
dp[i][j]:前i个分组在容量为觉得情况下的最大价值 dp[i][j]max(dp[i-1][j],dp[i-1][j-v]w)
代码实现1
#includeiostream
#includealgorithm
using namespace std;
#define MAX_N 1000
struct Data{int a,b,c;
}item[MAX_N5];
int dp[MAX_N5][MAX_N5];//此处为前i个物品容量为j的情况下的最大价值
bool cmp(Data a,Data b)
{return a.cb.c;
}
int main()
{int m,n;cinmn;for(int i1;in;i){cinitem[i].aitem[i].bitem[i].c;}sort(item1,itemn1,cmp);int cnt1;for(int i1;in;i){if(item[i].citem[i-1].c)cnt;else cnt1;for(int j1;jm;j){dp[i][j]dp[i-1][j];if(jitem[i].a)dp[i][j]max(dp[i][j],dp[i-cnt][j-item[i].a]item[i].b);}}coutdp[n][m];return 0;
}代码实现2
#includebits/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(){cinvn;for(i1;in;i){cinw[i]z[i]x;tmax(t,x);b[x];g[x][b[x]]i;}for(i1;it;i){for(jv;j0;j--){for(k1;kb[i];k){if(jw[g[i][k]]){dp[j]max(dp[j],dp[j-w[g[i][k]]]z[g[i][k]]);}}}}coutdp[v];return 0;
}[USACO09MAR] Cow Frisbee Team S
题目描述
老唐最近迷上了飞盘约翰想和他一起玩于是打算从他家的 N N N 头奶牛中选出一支队伍。
每只奶牛的能力为整数第 i i i 头奶牛的能力为 R i R_i Ri。飞盘队的队员数量不能少于 1 1 1、大于 N N N。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信他的幸运数字是 F F F所以他要求队伍的总能力必须是 F F F 的倍数。请帮他算一下符合这个要求的队伍组合有多少由于这个数字很大只要输出答案对 1 0 8 10^8 108 取模的值。
输入格式
第一行两个用空格分开的整数 N N N 和 F F F。
第二行到 N 1 N1 N1 行第 i 1 i1 i1 行有一个整数 R i R_i Ri表示第 i i i 头奶牛的能力。
输出格式
第一行单个整数表示方案数对 1 0 8 10^8 108 取模的值。
样例 #1
样例输入 #1
4 5
1
2
8
2样例输出 #1
3提示
对于 100 % 100\% 100% 的数据 1 ≤ N ≤ 2000 1 \le N \le 2000 1≤N≤2000 1 ≤ F ≤ 1000 1 \le F \le 1000 1≤F≤1000 1 ≤ R i ≤ 1 0 5 1 \le R_i \le 10^5 1≤Ri≤105。
解题思路
状态定义dp[i][j]:前i头牛对f取模为j的方案总数 转移方程dp[i][j]dp[i-1][j]dp[i-1][(j-val[i]%ff)%f] 特别注意对于每一个val[i]%f都要在dp[i][val[i]%f]的位置上加上一个1
代码实现
#includeiostream
using namespace std;
#define MAX_N 2000
#define MAX_F 1000
#define MOD 100000000
int dp[2][MAX_F5];
int val[MAX_N5];
int n,f;
int main()
{cinnf;for(int i1;in;i){cinval[i];val[i]%f;}int now0;for(int i1;in;i){for(int j0;jf;j){dp[now][j](dp[now^1][j]dp[now^1][(j-val[i]f)%f])%MOD;}dp[now][val[i]]1;now^1;}coutdp[now^1][0];return 0;}
垃圾陷阱
题目描述
卡门――农夫约翰极其珍视的一条 Holsteins 奶牛――已经落了到 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方它的深度为 D D D 2 ≤ D ≤ 100 2 \le D \le 100 2≤D≤100英尺。
卡门想把垃圾堆起来等到堆得与井深同样高或比井深更高即垃圾高度总和 ≥ D \geq D ≥D时她就能逃出井外了。另外卡门可以通过吃一些垃圾来维持自己的生命。
每个垃圾都可以用来吃或堆放并且堆放垃圾不用花费卡门的时间。
假设卡门预先知道了每个垃圾扔下的时间 t t t 1 ≤ t ≤ 1000 1 \le t \le 1000 1≤t≤1000以及每个垃圾堆放的高度 h h h 1 ≤ h ≤ 25 1 \le h \le 25 1≤h≤25和吃进该垃圾能增加维持生命的时间 f f f 1 ≤ f ≤ 30 1 \le f \le 30 1≤f≤30要求出卡门最早能逃出井外的时间假设卡门当前体内有足够持续 10 10 10 小时的能量如果卡门 10 10 10 小时内不含 10 10 10 小时维持生命的时间同没有进食卡门就将饿死。特别地若体力值为 0 0 0 时吃下垃圾或逃出井外也不会饿死。
输入格式
第一行为两个整数 D D D 和 G G G 1 ≤ G ≤ 100 1 \le G \le 100 1≤G≤100 G G G 为被投入井的垃圾的数量。
第二到第 G 1 G1 G1 行每行包括三个整数 T T T 1 ≤ T ≤ 1000 1 \le T \le 1000 1≤T≤1000表示垃圾被投进井中的时间 F F F 1 ≤ F ≤ 30 1 \le F \le 30 1≤F≤30表示该垃圾能维持卡门生命的时间和 H H H 1 ≤ H ≤ 25 1 \le H \le 25 1≤H≤25该垃圾能垫高的高度。
输出格式
如果卡门可以爬出陷阱输出一个整数表示最早什么时候可以爬出否则输出卡门最长可以存活多长时间。
样例 #1
样例输入 #1
20 4
5 4 9
9 3 2
12 6 10
13 1 1样例输出 #1
13提示
【样例说明】
卡门堆放她收到的第一个垃圾 h e i g h t 9 \mathrm{height}9 height9
卡门吃掉她收到的第 2 2 2 个垃圾使她的生命从 10 10 10 小时延伸到 13 13 13 小时
卡门堆放第 3 3 3 个垃圾 h e i g h t 19 \mathrm{height}19 height19
卡门堆放第 4 4 4 个垃圾 h e i g h t 20 \mathrm{height}20 height20。
解题思路
状态定义dp[i][j]表示前i个垃圾在能量为j的情况下的最大高度 转移方程dp[i][j]max(dp[i-1][j],dp[i-1][j-f]h)
代码实现
#includeiostream
#includealgorithm
using namespace std;
#define MAX_D 100
#define MAX_G 100
int d,g;
struct Data{int t,f,h;
}rubbish[MAX_G5];
int dp[MAX_G5][3010];
int vis[MAX_G5][3010];
bool cmp(Data a,Data b)
{return a.tb.t;
}
int main()
{cindg;int max_t0,sum_f10;for(int i1;ig;i){cinrubbish[i].trubbish[i].frubbish[i].h;max_tmax(max_t,rubbish[i].t);sum_frubbish[i].f;}sort(rubbish1,rubbish1g,cmp);if(rubbish[1].t10){dp[1][10]rubbish[1].h;if(rubbish[1].t!10)vis[1][10]1;vis[1][10rubbish[1].f]1;if(rubbish[1].hd){coutrubbish[1].t;return 0;}}for(int i2;ig;i){for(int j10;jsum_f;j){if(jrubbish[i].t)continue;if((j-rubbish[i].f)rubbish[i].tvis[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){coutrubbish[i].t;return 0;}}}int last10;for(int i1;ig;i){if(lastrubbish[i].t)lastrubbish[i].f;else{coutlast;return 0;}}coutlast;return 0;}
[BJOI2019] 排兵布阵
题目描述
小 C 正在玩一款排兵布阵的游戏。在游戏中有 n n n 座城堡每局对战由两名玩家来争夺这些城堡。每名玩家有 m m m 名士兵可以向第 i i i 座城堡派遣 a i a_i ai 名士兵去争夺这个城堡使得总士兵数不超过 m m m。
如果一名玩家向第 i i i 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍那么这名玩家就占领了这座城堡获得 i i i 分。
现在小 C 即将和其他 s s s 名玩家两两对战这 s s s 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 s s s 名玩家即将使用的策略他想知道他应该使用什么策略来最大化自己的总分。
由于答案可能不唯一你只需要输出小 C 总分的最大值。
输入格式
输入第一行包含三个正整数 s , n , m s,n,m s,n,m分别表示除了小 C 以外的玩家人数、城堡数和每名玩家拥有的士兵数。 接下来 s s s 行每行 n n n 个非负整数表示一名玩家的策略其中第 i i i 个数 a i a_i ai 表示这名玩家向第 i 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 1 1 座城堡和第 2 2 2 座城堡各派遣 5 5 5 名士兵。
样例2解释 小 C 的最佳策略之一为向第 1 1 1 座城堡派遣 2 2 2 名士兵向第 2 2 2 座城堡派遣 5 5 5 名士兵向第 3 3 3 座城堡派遣 1 1 1 名士兵。
数据范围 对于 10 % 10\% 10% 的数据 s 1 , n ≤ 3 , m ≤ 10 s1,n \le 3,m \le 10 s1,n≤3,m≤10 对于 20 % 20\% 20% 的数据 s 1 , n ≤ 10 , m ≤ 100 s1,n \le 10,m \le 100 s1,n≤10,m≤100 对于 40 % 40\% 40% 的数据 n ≤ 10 , m ≤ 100 n\le 10,m\le 100 n≤10,m≤100 对于另外 20 % 20\% 20% 的数据 s 1 s1 s1 对于 100 % 100\% 100% 的数据 1 ≤ s ≤ 100 1\le s \le 100 1≤s≤100 1 ≤ n ≤ 100 1\le n \le 100 1≤n≤100 1 ≤ m ≤ 20000 1\le m \le 20000 1≤m≤20000 对于每名玩家 a i ≥ 0 a_i \ge 0 ai≥0 ∑ i 1 n a i ≤ m \sum\limits_{i1}^n a_i \le m i1∑nai≤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的对应关系单独处理
代码实现
#includeiostream
#includealgorithm
#includevector
using namespace std;
#define MAX_S 100
#define MAX_N 100
#define MAX_M 20000
int bing[MAX_S5][MAX_N5];
int dp[MAX_N5][MAX_M5];
vectorpairint,intg[MAX_N5];
int s,n,m;
int main()
{cinsnm;for(int i1;is;i){for(int j1;jn;j){cinbing[j][i];}}for(int i1;in;i)sort(bing[i]1,bing[i]1s);for(int i1;in;i){for(int j1;js;j){if(bing[i][j]bing[i][j1])continue;if(bing[i][j]*2m)break;g[i].push_back(make_pair(bing[i][j]*21,j));}if(bing[i][s]0)g[i].push_back(make_pair(1,s));}for(int i1;in;i){for(int j1;jm;j){dp[i][j]dp[i-1][j];for(auto k:g[i])if(jk.first)dp[i][j]max(dp[i][j],dp[i-1][j-k.first]i*k.second);}}coutdp[n][m];return 0;
}总结背包问题的一般形式为在若干个物品中按照一定的逻辑选择若干个或者对于每一个物品选择其某一个属性t4或者对于某一个物品使用多大的代价选择其多大的部分t5等等以求最后效益最大。
