[HDU-1114 Piggy-Bank] 完全背包裸题

http://acm.hdu.edu.cn/showproblem.php?pid=1114

一道迷路的完全背包跑到了这里来...相当于给定背包大小，然后问装满之后最多的价值。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e4+5; int val[505], w[505]; int dp[maxn]; int main() { int t; scanf("%d", &t); while(t--) { int a, b, n, m; scanf("%d%d", &a, &b); n = b-a; scanf("%d", &m); for(int i = 1; i <= m; i++) { scanf("%d%d", &val[i], &w[i]); } memset(dp, inf, sizeof(dp)); dp[0] = 0; for(int i = 1; i <= m; i++) { for(int j = w[i]; j <= n; j++) { dp[j] = min(dp[j], dp[j-w[i]]+val[i]); } } if(dp[n] == inf) { printf("This is impossible.\n"); } else { printf("The minimum amount of money in the piggy-bank is %d.\n", dp[n]); } } return 0; }

[HDU-1059 Dividing] 多重背包裸题

http://acm.hdu.edu.cn/showproblem.php?pid=1059

给定 1~6 这六个数的数量，问能不能把这些数分成价值相同的两堆。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 2e5+5; int val[7], num[7]; int dp[maxn]; int main() { for(int i = 1; i <= 6; i++) { val[i] = i; } int cas = 1; while(~scanf("%d%d%d%d%d%d", &num[1], &num[2], &num[3], &num[4], &num[5], &num[6])) { if(num[1]+num[2]+num[3]+num[4]+num[5]+num[6] == 0) { break; } printf("Collection #%d:\n", cas++); int sum = 0; for(int i = 1; i <= 6; i++) { sum += (num[i]*val[i]); } if(sum % 2 == 1) { printf("Can't be divided.\n\n"); continue; } sum = sum/2; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= 6; i++) { if(val[i]*num[i] >= sum) { for(int j = val[i]; j <= sum; j++) { dp[j] = max(dp[j], dp[j-val[i]]+val[i]); } } else { int k = 1; while(k < num[i]) { for(int j = sum; j >= k*val[i]; j--) { dp[j] = max(dp[j], dp[j-k*val[i]]+k*val[i]); } num[i] -= k; k *= 2; } for(int j = sum; j >= num[i]*val[i]; j--) { dp[j] = max(dp[j], dp[j-num[i]*val[i]]+num[i]*val[i]); } } } if(dp[sum] == sum) { printf("Can be divided.\n\n"); } else { printf("Can't be divided.\n\n"); } } return 0; }

[HDU-2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活] 多重背包裸题

http://acm.hdu.edu.cn/showproblem.php?pid=2191

买米，给定每种米的价格、价值和数量，问给你的钱最多能买到多少价值的米。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; int v[105], w[105], c[105]; int dp[105]; int main() { int t; scanf("%d", &t); while(t--) { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &v[i], &w[i], &c[i]); } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= m; i++) { if(v[i]*c[i] >= n) { for(int j = v[i]; j <= n; j++) { dp[j] = max(dp[j], dp[j-v[i]]+w[i]); } } else { int k = 1; while(k < c[i]) { for(int j = n; j >= k*v[i]; j--) { dp[j] = max(dp[j], dp[j-k*v[i]]+k*w[i]); } c[i] -= k; k *= 2; } for(int j = n; j >= c[i]*v[i]; j--) { dp[j] = max(dp[j], dp[j-c[i]*v[i]]+c[i]*w[i]); } } } printf("%d\n", dp[n]); } return 0; }

[POJ-1276 Cash Machine] 多重背包裸题

http://poj.org/problem?id=1276

题意...记不太得了..反正是裸题就对了。不想上代码了。

[POJ-2392 Space Elevator] 多重背包变形

http://poj.org/problem?id=2392

给定几种砖块，每种砖块都有自己的高度、数量和超过xx高度就不能用的属性（ai）。问最高能叠到多少。

在传统多重背包的基础上，需要按照 ai 排序，又因为不定最大值，所以需要给定理论上界来进行循环，就这样。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; struct node { int h, a, c; bool operator < (const node &y) const { return a < y.a; } }x[405]; int dp[40005]; int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) { scanf("%d%d%d", &x[i].h, &x[i].a, &x[i].c); } sort(x+1, x+1+n); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { if(x[i].h*x[i].c > 40000) { for(int j = x[i].h; j <= 40000; j++) { if(j > x[i].a) break; dp[j] = max(dp[j], dp[j-x[i].h]+x[i].h); } } else { int k = 1; while(k < x[i].c) { for(int j = 40000; j >= k*x[i].h; j--) { if(j > x[i].a) continue; dp[j] = max(dp[j], dp[j-k*x[i].h]+k*x[i].h); } x[i].c -= k; k *= 2; } for(int j = 40000; j >= x[i].h*x[i].c; j--) { if(j > x[i].a) continue; dp[j] = max(dp[j], dp[j-x[i].h*x[i].c]+x[i].h*x[i].c); } } } int ans = 0; for(int i = 40000; i >= 0; i--) { if(dp[i] == i) { ans = i; break; } } printf("%d\n", ans); } return 0; }

[HDU-1712 ACboy needs your help] 分组背包裸题

http://acm.hdu.edu.cn/showproblem.php?pid=1712

有 m 天复习 n 门课程，每天只能复习一门课。并且给定课程 i 复习 j 天获得的价值，问最多能获得多少价值。

分组背包顾名思义，在背包里面的物品是分成不同组的，每个组只能取一件物品。类似于01背包的做法，很容易想到，背包的容量一定是从大到小递推才能保证每组物品只取一个。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; int a[105][105]; int dp[105]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { if(n+m == 0) { break; } memset(a, 0, sizeof(a)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { for(int j = m; j >= 0; j--) { for(int k = 1; k <= j; k++) { dp[j] = max(dp[j], dp[j-k]+a[i][k]); } } } printf("%d\n", dp[m]); } return 0; }

[HDU-3033 I love sneakers!] 分组背包变形

http://acm.hdu.edu.cn/showproblem.php?pid=3033

买球鞋，给定球鞋数量 n、支付宝金额 m、球鞋种类 k。每双球鞋都有种类、价值、花费。要求是每种球鞋都要至少买一个，求最大价值。

分组背包问题一般是每组最多选一件，这里是选至少一件，我们需要对每组进行01背包。当前第 k 组的时候在里面选择物品的时候是选的第几件。如果我们当前是选第 k 组中的第一件，那么是从第 k-1 组推过来的；否则就是第 k 组中的前一件 (i-1) 推过来的。初始化是，如果一开始把 dp 初始化为0，则当所有鞋子的价值都是 0 时，就无法区分是买不全那几款鞋子还是能买全但最大价值是0。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e4+5; int dp[105][maxn]; // dp[k][i] 表示前 k 组中花费 i 取得的最大价值 int b[105], w[105], v[105]; int main() { int n, m, k; while(~scanf("%d%d%d", &n, &m, &k)) { for(int i = 1; i <= n; i++) { scanf("%d%d%d", &b[i], &w[i], &v[i]); } memset(dp, -1, sizeof(dp)); for(int i = 0; i <= m; i++) { dp[0][i] = 0; } for(int x = 1; x <= k; x++) { for(int i = 1; i <= n; i++) { if(b[i] == x) { for(int j = m; j >= w[i]; j--) { dp[x][j] = max(dp[x][j], max(dp[x][j-w[i]]+v[i], dp[x-1][j-w[i]]+v[i])); } } } } if(dp[k][m] == -1) { printf("Impossible\n"); } else { printf("%d\n", dp[k][m]); } } return 0; }

[POJ-1837 Balance] 分组背包变形

http://poj.org/problem?id=1837

输入 n 表示天平上有几个挂钩、m 表示有几个挂码。给定每个挂钩的位置（a），负数表示在左侧，正数表示在右侧。给定每个挂码的重量（b）。问有几种方法可以使得天平平衡。

由数据范围可知，天平左右两端力矩最大值都是 201525=7500。因此用[0, 15000] 表示力矩的范围，7500表示平衡状态。初始化0个砝码时，到达平衡状态7500时的方案数为1。

达到每种状态时的方案数，需要从 1 个挂码到有 m 个挂码的状态进行转移。因此可以类似背包问题的方法求解，有状态转移方程 \(dp[i][j+b[i]*a[k]] += dp[i-1][j]\)。 表示第 i 个砝码是新加入的，砝码 i 悬挂的位置用 k 表示有1~n个。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 20*15*25*2+5; int a[25], b[25]; // a 挂钩位置、b 物体重量 int dp[25][maxn]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = 1; i <= m; i++) { scanf("%d", &b[i]); } memset(dp, 0, sizeof(dp)); dp[0][7500] = 1; for(int i = 1; i <= m; i++) { for(int j = 1; j <= 15000; j++) { for(int k = 1; k <= n; k++) { dp[i][j+a[k]*b[i]] += dp[i-1][j]; } } } printf("%d\n", dp[m][7500]); } return 0; }

[POJ-3211 Washing Clothes] 分组背包变形

http://poj.org/problem?id=3211

先记录每种颜色所代表的衣服洗干净所用的时间。对于第 i 颜色，用01背包找到0到 sum[i]/2 ，洗衣服时可能遇到所有时间点，在找到 0 到 sum[i]/2 中最大的时间点 j ，则 sum[i]-j 则是洗第 i 种颜色的衣服所用的最少时间。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; string s[15]; int cnt[15], sum[15]; int t[15][105]; int dp[50005]; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { if(n+m == 0) { break; } memset(cnt, 0, sizeof(cnt)); memset(sum, 0, sizeof(sum)); memset(t, 0, sizeof(t)); for(int i = 1; i <= n; i++) { cin >> s[i]; } for(int i = 1; i <= m; i++) { int a; string str; cin >> a >> str; for(int j = 1; j <= n; j++) { if(str == s[j]) { t[j][cnt[j]] = a; sum[j] += a; cnt[j] ++; break; } } } int ans = 0; for(int i = 1; i <= n; i++) { memset(dp, 0, sizeof(dp)); dp[0] = 1; for(int j = 0; j < cnt[i]; j++) { for(int k = sum[i]/2; k >= t[i][j]; k--) { dp[k] |= dp[k-t[i][j]]; } } int temp; for(temp = sum[i]/2; temp >= 0; temp--) { if(dp[temp]) { break; } } temp = sum[i] - temp; ans += temp; } printf("%d\n", ans); } return 0; }

[HDU-3810 Magina] 分组背包 + 双优先队列优化

http://acm.hdu.edu.cn/showproblem.php?pid=3810

dota敌法师的技能闪烁无CD。他现在要刷野区赚钱，每个野怪营地需要花费 t 时间赚取 g 赏金。存在一些点之间可以用闪烁技能到达。问能否在赚到给定金钱，并求出最小时间。

把能够相互到达的点可以看成一部分，那么就分成很多部分，每个部分没有任何联系，相互做一次01背包，取最小值就行。

问题的关键是本题数据很大，背包容量最大是10亿，虽然给了30s，但是数组和普通队列都存不下。所以需要剪枝，比如说时间都已经超过了中间临时的最小时间的，肯定不用继续搜下去了，还有当前容量占用小，时间花费长的肯定要剪掉，那么一个好的方法是优先队列，可以很方便的剪掉刚才说的第二种无用状态。

故用两个优先队列，类似与滚动数组的思路，第一个存放当前状态，第二个存放能够转移得到的状态，然后再把转移得到的状态剪掉一部分后放回第一个队列。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 55; int cnt[maxn], vis[maxn]; int road[maxn][maxn]; int mp[maxn][maxn]; int n, m, ans; int tot; struct NODE { int t, g; bool operator < (const NODE &a) const { if(g == a.g) { return t > a.t; } return g < a.g; } }node[maxn]; void init() { memset(mp, 0, sizeof(mp)); memset(cnt, 0, sizeof(cnt)); memset(vis, 0, sizeof(vis)); memset(road, 0, sizeof(road)); ans = inf; tot = 0; } void dfs(int x) { for(int i = 1; i <= n; i++) { if(vis[i] == 0 && mp[x][i] == 1) { vis[i] = 1; road[tot][cnt[tot]++] = i; dfs(i); } } } void solve() { for(int i = 0; i < tot; i++) { priority_queue<NODE> q1, q2; NODE now, nxt; now.t = now.g = 0; q1.push(now); for(int j = 0; j < cnt[i]; j++) { while(!q1.empty()) { now = q1.top(); q1.pop(); q2.push(now); nxt.t = now.t + node[road[i][j]].t; nxt.g = now.g + node[road[i][j]].g; if(nxt.g >= m) { ans = min(ans, nxt.t); } else if(nxt.t < ans) { q2.push(nxt); } } int temp = inf; while(!q2.empty()) { now = q2.top(); q2.pop(); if(temp >= now.t) { q1.push(now); temp = now.t; } } } } } int main() { int t, cas = 1; scanf("%d", &t); while(t--) { init(); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { int x; scanf("%d%d%d", &node[i].t, &node[i].g, &x); for(int j = 1; j <= x; j++) { int y; scanf("%d", &y); mp[i][y] = mp[y][i] = 1; } } for(int i = 1; i <= n; i++) { if(vis[i] == 0) { vis[i] = 1; road[tot][cnt[tot]++] = i; dfs(i); tot++; } } solve(); printf("Case %d: ", cas++); if(ans == inf) { printf("Poor Magina, you can't save the world all the time!\n"); } else { printf("%d\n", ans); } } return 0; }

[HDU-3535 AreYouBusy] 综合背包

http://acm.hdu.edu.cn/showproblem.php?pid=3535

n 种工作集合、给 t 时间。工作集合分为 3 类（s =【0至少做一件】、【1至多做一件】、【2无限制】），每种集合有 m 个事件（用时 w、价值 v）。求能获得的最大价值。

用背包思想单独处理每个集合。\(dp[i][j]==x\) 表示处理完前 i 组工作集合，所花时间 <=j 时的快乐值为 x 。

至少做一件：要保证至少选 1 个第 i 类事件，可以从第 i-1 类的结果 dp[i-1] 来更新 dp[i] ；也可以从本类的前一个事件更新后一个事件。初始化：\(dp[i] = -inf\)。状态转移方程：\[dp[i][k] = max(dp[i][k], max(dp[i][k-w[j]]+v[j], dp[i-1][k-w[j]]+v[j]))\]

至多做一件：只能从 dp[i-1] 来更新 dp[i] 。初始化：\(dp[i]=dp[i-1]\)。状态转移方程：\[dp[i][k] = max(dp[i][k], dp[i-1][k-w[j]]+v[j])\]

无限制：初始化：\(dp[i]=dp[i-1]\)。状态转移方程：\[dp[i][k] = max(dp[i][k], dp[i][k-w[j]]+v[j])\]

最终所求：\(dp[n][t]\)。

#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <bitset> #include <cctype> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <fstream> #include <iomanip> #include <numeric> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const double PI = acos(-1.0); const double eps = 1e-6; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e2+5; int dp[maxn][maxn]; int w[maxn], v[maxn]; int main() { int n, t; while(~scanf("%d%d", &n, &t)) { memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) { int m, s; scanf("%d%d", &m, &s); for(int j = 1; j <= m; j++) { scanf("%d%d", &w[j], &v[j]); } if(s == 0) { // 至少选择一个做 for(int j = 0; j <= t; j++) { dp[i][j] = -inf; } for(int j = 1; j <= m; j++) { for(int k = t; k >= w[j]; k--) { dp[i][k] = max(dp[i][k], max(dp[i][k-w[j]]+v[j], dp[i-1][k-w[j]]+v[j])); } } } else if(s == 1) { // 至多选择一个做 for(int j = 0; j <= t; j++) { dp[i][j] = dp[i-1][j]; } for(int j = 1; j <= m; j++) { for(int k = t; k >= w[j]; k--) { dp[i][k] = max(dp[i][k], dp[i-1][k-w[j]]+v[j]); } } } else { // 随便选 for(int j = 0; j <= t; j++) { dp[i][j] = dp[i-1][j]; } for(int j = 1; j <= m; j++) { for(int k = t; k >= w[j]; k--) { dp[i][k] = max(dp[i][k], dp[i][k-w[j]]+v[j]); } } } } int ans = -1; ans = max(dp[n][t], ans); printf("%d\n", ans); } return 0; }

转载于:https://www.cnblogs.com/Decray/p/11197182.html