首页 > 代码库 > 背包九讲 && 题目
背包九讲 && 题目
1、01背包问题。
tot：总背包空间，vall[i]：每件物品的价值，w[i]：每件物品的重量
http://acm.hdu.edu.cn/showproblem.php?pid=2602
01背包明显可以只写一维的，所以二维的就不写了。
关于为什么可以只写一维的呢？这就和你枚举的顺序有关了。从tot 枚举 到 w[i]。那么是优先更新dp[比较大的数]
而且是从dp[i - 1][]那里更新过来的。至于后面枚举小的背包容量的时候，较大的背包容量是用不了的了，所以这里就可以避免有重复使用的bug。确保都是从dp[i- 1]枚举过来。而这个顺序反转了的话，刚好的完全背包的最优解。这个后面再说
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e3 + 20; int dp[maxn]; int w[maxn], val[maxn]; void work() { memset(dp, 0, sizeof dp); int n, tot; scanf("%d%d", &n, &tot); for (int i = 1; i <= n; ++i) { scanf("%d", &val[i]); } for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); } for (int i = 1; i <= n; ++i) { for (int j = tot; j >= w[i]; --j) { dp[j] = max(dp[j], dp[j -w[i]] + val[i]); } } printf("%d\n", dp[tot]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
一个常数的优化：
我把tot加大到10000.然后提交就变成了655ms。下面来说说当总背包容量tot比较大的时候，该怎么优化。
对于第n件物品，我们的转移方程是dp[tot] = max(dp[tot], dp[tot - w[n]); //这个就是答案
其实只需要一步就够了，因为我们需要的是dp[tot]，不用再向下枚举了。但是根据上面的代码，是需要枚举到
for (j := tot; j >= w[n]; --j)，是需要枚举到w[n]的，为什么呢？其实是为了给后面的做铺垫。因为我们并不知道这个是最后的一个背包，所以还是需要枚举到w[i]的，因为后面的背包可能需要用到dp[w[i]]这个背包的值。来更新最优解
那么我们可以算出一个下限，什么下限呢，就是后面的所有可能的背包中，最多需要用到那一个背包。
对于最后一个背包，他只需要用到dp[tot - w[n]]这个背包就够了。枚举到倒数第二种物品的时候，
他只需要用到dp[tot - w[n] - w[n - 1]]这个背包就够了。那么前面的背包，我们就不需要更新了。
感觉还是写张图比较好理解，以免我以后忘记。
现在考虑枚举到了倒数第二种物品，我们只需要更新红色那个区域就行了，因为最后一个物品只需要用到dp[tot - w[n]]
那么同理，需要更新红色那段区域，我们只需要知道[tot - w[n] - w[n - 1], tot]这段区域的最优值是谁就可以了，因为我们为了更新红色那段区域，对于倒数第二种物品，其重量是w[i]，下限就是tot - w[n] - w[i]，故按照这个思路递推回去第i件物品即可。
这个用来优化当tot比较大的时候，是有用的，我把tot和w[]都同时加上了一个fix值，结果TLE，不是TLE就是RE。还是找到合适的题目再写上来吧，
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e3 + 20; int dp[maxn]; int w[maxn], val[maxn]; int suffix_sum[maxn]; void work() { memset(dp, 0, sizeof dp); int n, tot; scanf("%d%d", &n, &tot); for (int i = 1; i <= n; ++i) { scanf("%d", &val[i]); } for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); } suffix_sum[n + 1] = 0; for (int i = n; i >= 1; --i) { suffix_sum[i] = w[i] + suffix_sum[i + 1]; } for (int i = 1; i <= n; ++i) { int toUpdate = max(w[i], tot - suffix_sum[i + 1]); for (int j = tot; j >= toUpdate; --j) { dp[j] = max(dp[j], dp[j -w[i]] + val[i]); } } printf("%d\n", dp[tot]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
关于dp的初始化。开始的时候dp[0] = 0表示容量为0的背包，能得到物品的价值是0.后面的就有两类了。
①、需要刚好装满tot个，那么，后面的就是全部都是-inf了，表示刚好刚好装满x个的时候，价值是负的，就是没有价值。
②、不需要的话，就全部都是0.
二维01背包，
POJ 1948
http://poj.org/problem?id=1948
给定n根木棒，要求全部用上，组成一个三角形，使得这个三角形的面积最大。
dp[i][j]表示组成的第一根木棒长度是i的时候，第二根木棒长度是j，第三根木棒的长度是dp[i][j]
那么对于周长是固定的话，那么dp数组开bool的就够了。dp[i][j] = 0表示这个方案不可行
比如dp[0][1] = true。表示第一根木棒是0，第二根木棒是1，第三根是all - 0 - 1。那么就全部木棒也用上了。
转移的话，if (dp[i][j]) then dp[i + val][j] = true; dp[i][j + val] = true;
就是这个物品，可以去两组中的任意一组，都可以。
同样也是枚举顺序的问题，应该倒着来枚举，因为木棒只能用一次。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1600 + 20; bool dp[maxn][maxn]; int a[maxn]; bool check (int a, int b, int c) { if (abs(a - b) >= c) return false; if (abs(a - c) >= b) return false; if (abs(b - c) >= a) return false; return true; } double calc(double a, double b, double c) { // cout << a << " " << b << " " << c << endl; double p = (a + b + c) / 2.0; // cout << p << endl; double ans = sqrt(p * (p - a) * (p - b) * (p - c)); return ans * 100; } void work() { int n; int all = 0; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); all += a[i]; } // dp[0][0] = dp[a[1]][0] = dp[0][a[1]] = true; dp[0][0] = true; int en = (all + 1) / 2; for (int i = 1; i <= n; ++i) { for (int j = en; j >= 0; --j) { for (int k = en; k >= j; --k) { if (j >= a[i] && dp[j - a[i]][k]) { dp[j][k] = true; } if (k >= a[i] && dp[j][k - a[i]]) { dp[j][k] = true; } } } } int ans = -1; for (int i = 1; i <= en; ++i) { for (int j = i; j <= en; ++j) { if (dp[i][j] && check(i, j, all - i - j)) { ans = max(ans, (int)calc(i, j, all - i - j)); } } } printf("%d\n", ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
2、完全背包
关于完全背包，唯一需要变的就是枚举的方向，使得同一个物品能被多次使用。
http://acm.hdu.edu.cn/showproblem.php?pid=1114
因为需要恰好装满，所以初始化需要改变一下。
完全背包的题目，要求输出最小价值。然后一定要把给出的背包重量全部用完。
就是问一个背包为k的大小，n件物品，能装的最小价值，并且一定是用了k个背包容量。
用dp[i]表示背包容量为i得时候，能收录的最小价值，
边界：dp[0] = 0； 没容量，啥都干不了
else dp[i] = inf。一开始初始化为无穷大。
转移的话,dp[i] = min(dp[i], dp[i - weight[j]] + val[j])
枚举的话，次循环要顺着枚举。
因为这样才能确保它是能使用多次（完全背包嘛）
为什么顺着枚举就可以了呢？
因为考虑一下，当物品的重量为5，背包重量是10的时候。
顺着枚举for (int j = 5; j <= 10; ++j) 的话，
j = 5的时候，物品能枚举到是否加入背包，然后j = 10的时候，物品再次被枚举是否加入这个背包，也就是重复使用了
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 10000 + 20; int dp[maxn]; int w[maxn]; int val[maxn]; void work() { int a, b; scanf("%d%d", &a, &b); int tot = b - a; int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &val[i], &w[i]); } memset(dp, 0x3f, sizeof dp); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = w[i]; j <= tot; ++j) { dp[j] = min(dp[j], dp[j - w[i]] + val[i]); } } if (dp[tot] == inf) { cout << "This is impossible." << endl; } else { printf("The minimum amount of money in the piggy-bank is %d.\n", dp[tot]); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
3、多重背包问题
有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1086
对于一个物品，如果他有c[i]件，那么我可以把它拆成2^0 + 2^1 + 2^k... + (c[i] - 2^(k + 1) + 1)
这样使得它转化为01背包问题后，任选一些，都能凑合成 <= c[i]的任何数字。
比如14 = 1 + 2 + 4 + 7。只有log个
这样就能结合到1--14之间的所有数字，为什么呢，因为1 + 2 + 4是能组合成1 -- 7之间的任何数字的了，这是根据二进制的思想。
1
10
100
每个东西的位置“1”，都可以要，与不要，所以能组合成1---7的任何数字，然后这些数字和剩下的那个7,一结合，就是1--14的任何数字
然后转化成01背包求解。
复杂度是O(vn)的，现在n有sigma(log(c[i]))个。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> struct node { int val; int w; node(int aa, int bb) : val(aa), w(bb) {} node() {} }a[100 * 200 + 20]; const int maxn = 50000 + 20; int dp[maxn]; void work() { int n, tot; scanf("%d%d", &n, &tot); int lena = 0; for (int i = 1; i <= n; ++i) { int w, p, c; scanf("%d%d%d", &w, &p, &c); for (int i = 0; i <= 31; ++i) { if ((1 << i) < c) { c -= (1 << i); a[++lena] = node((1 << i) * p, (1 << i) * w); } else { a[++lena] = node(p * c, w * c); break; } } } for (int i = 1; i <= lena; ++i) { for (int j = tot; j >= a[i].w; --j) { dp[j] = max(dp[j], dp[j - a[i].w] + a[i].val); } } cout << dp[tot] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
这个题目，可以使用上面说的一个常数的优化，使得变成62ms
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> struct node { int val; int w; node(int aa, int bb) : val(aa), w(bb) {} node() {} }a[100 * 200 + 20]; const int maxn = 50000 + 20; int dp[maxn]; int suffix_sum[maxn]; void work() { int n, tot; scanf("%d%d", &n, &tot); int lena = 0; for (int i = 1; i <= n; ++i) { int w, p, c; scanf("%d%d%d", &w, &p, &c); for (int i = 0; i <= 31; ++i) { if ((1 << i) < c) { c -= (1 << i); a[++lena] = node((1 << i) * p, (1 << i) * w); } else { a[++lena] = node(p * c, w * c); break; } } } for (int i = lena; i >= 1; --i) { suffix_sum[i] = a[i].w + suffix_sum[i + 1]; } for (int i = 1; i <= lena; ++i) { int toUpdate = max(a[i].w, tot - suffix_sum[i + 1]); for (int j = tot; j >= toUpdate; --j) { dp[j] = max(dp[j], dp[j - a[i].w] + a[i].val); } } cout << dp[tot] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
4、混合三种背包问题
留坑
5、二维费用背包问题
这类问题就是，对于每一个物品，都有两种不同的费用，a[i]和b[i]，如果选取这个物品，就需要扣除分别的费用，现在给你两种不同的费用的总值，u和v，要求算出在不超过u和v的前提下能得到的最大价值。
所以可以设dp[i][j][k]表示前i种物品，第一种价值的背包容量是j，第二种背包容量是k时，得到的最大值。
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a[i]][k - b[i]] + val[i]);
那么怎么来枚举呢？枚举是有一定的顺序的。
第一，先枚举每件物品，因为每件物品只能选一次，就选能选多次，也是后面维度的枚举顺序要变化。
第二，枚举第三维。
第三，枚举第二维。
为什么需要这样呢？我们结合一个例题
http://acm.tju.edu.cn/toj/showp3596.html
给定n个物品，选出确定的m个，拥有背包容量为L。求最大价值。
设dp[m][L]表示选出了m件物品，背包容量为L时的最大价值。这里我省略了一维
第一，先枚举每件物品，看起来十分好理解，因为不能重新选择嘛。
至于为什么要先枚举第三维，那么我们先来枚举第二维，看看会怎样，结合题目的那个样例。
先枚举选出了k个物品，然后再枚举背包容量为j时得到的最大价值。
for (int i = 1; i <= n; ++i) { //枚举物品
for (int k = 1; k <= min(i, m); ++k) { //枚举在前i个物品中，选了k个
for (int j = L; j >= w[i]; --j) { //枚举背包容量
dp[k][j] = max(dp[k][j], dp[k - 1][j - w[i]] + val[i]);
}
}
}
这样，模拟一下样例的话，是会算重的，dp[1][L]的时候选择了一次物品2，dp[1][L - 物品2的时间]也能选取物品2
那么这个时候dp[2][L] = max(dp[2][L], dp[1][L - 物品2的时间] + val[2])；//这里会算重复。
那么反过来，先枚举背包容量是j，再枚举选出了k件物品。
那么dp[1][L]根据dp[0][L - w[2]]算出，dp[2][L]根据dp[1][L - w[2]]算出，这个时候dp[1][L - w[2]]还没更新，所以不会算重复。
因为题目需要的是一定选出m个，那么dp[0][0...L] = 0，其他是-inf
因为，任何价值的背包，选出0个物品，都是没有价值的。
那为什么dp[1][0...L]是-inf呢。这是为了dp[2][L]从dp[1][]转移过来的时候，不会有价值，因为如果选取不了1个的话，是不能选取到2个的。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100 + 20; int Ti[maxn]; int Vi[maxn]; int dp[maxn][1000 + 20]; void work() { int n, m, L; scanf("%d%d%d", &n, &m, &L); for (int i = 1; i <= n; ++i) { scanf("%d%d", &Ti[i], &Vi[i]); } for (int i = 0; i <= m; ++i) { for (int j = 0; j <= L; ++j) { dp[i][j] = -inf; } } for (int i = 0; i <= L; ++i) { dp[0][i] = 0; //初始化 } for (int i = 1; i <= n; ++i) { //枚举物品为先，只能选一次 for (int j = L; j >= Ti[i]; --j) { for (int k = 1; k <= min(i, m); ++k) { dp[k][j] = max(dp[k][j], dp[k - 1][j - Ti[i]] + Vi[i]); } } } if (dp[m][L] < 0) dp[m][L] = 0; cout << dp[m][L] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
现在发现，上面说的枚举顺序有问题，其实是我对背包问题了解的不透。不好意思了
如果要防止dp[2][L]使用了dp[1][L - w[2]]（已更新）的话，那么可以把m倒着来枚举，这个就是上面的01背包的枚举顺序，因为一开始我觉得m一定是1--min(当前物品个数，m）的嘛，因为i个物品就不能选出m个了。但是倒着枚举，这些都是-inf，是没事的。
下面这个才是二维费用背包的01背包写法。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100 + 20; int Ti[maxn]; int Vi[maxn]; int dp[maxn][1000 + 20]; void work() { int n, m, L; scanf("%d%d%d", &n, &m, &L); for (int i = 1; i <= n; ++i) { scanf("%d%d", &Ti[i], &Vi[i]); } for (int i = 0; i <= m; ++i) { for (int j = 0; j <= L; ++j) { dp[i][j] = -inf; } } for (int i = 0; i <= L; ++i) { dp[0][i] = 0; //初始化 } for (int i = 1; i <= n; ++i) { for (int k = m; k >= 1; --k) { for (int j = L; j >= Ti[i]; --j) { dp[k][j] = max(dp[k][j], dp[k - 1][j - Ti[i]] + Vi[i]); } } } if (dp[m][L] < 0) dp[m][L] = 0; cout << dp[m][L] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=2159
二维费用背包 + 多重背包问题。
dp[s][m]表示前i种怪物，最多杀s个怪，拥有m点忍耐度，所得到的最大经验，
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n, m, k, s; const int maxn = 1e2 + 20; int dp[maxn][maxn]; int a[maxn]; int b[maxn]; void work() { memset(dp, 0, sizeof dp); for (int i = 1; i <= k; ++i) { scanf("%d%d", &a[i], &b[i]); } for (int i = 1; i <= k; ++i) { for (int j = 1; j <= s; ++j) { for (int h = b[i]; h <= m; ++h) { dp[j][h] = max(dp[j][h], dp[j - 1][h - b[i]] + a[i]); } } } if (dp[s][m] < n) { printf("-1\n"); } else { for (int i = 1; i <= m; ++i) { if (dp[s][i] >= n) { printf("%d\n", m - i); return; } } } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d%d%d", &n, &m, &k, &s) > 0 ) work(); return 0; }
https://vijos.org/p/1334
二维费用背包 + 01背包
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 400 + 20; int v[maxn]; int w[maxn]; int val[maxn]; int dp[maxn][maxn]; void work() { int n; int totv, totw; scanf("%d%d", &totv, &totw); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", &v[i], &w[i], &val[i]); } for (int i = 1; i <= n; ++i) { for (int j = totv; j >= v[i]; --j) { for (int k = totw; k >= w[i]; --k) { dp[j][k] = max(dp[j][k], dp[j - v[i]][k - w[i]] + val[i]); } } } cout << dp[totv][totw] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
分组背包问题
分组背包，没一个组只能选一个的话，那么设dp[k][v]表示前k组中，背包容量是v时的最大价值
那么转移就是，枚举组k中的每一个新元素，最多只有一个进来，那么就是
dp[k][v] = max(dp[k - 1][v], dp[k - 1][v - w[i]] + val[i])
for () //枚举每一个组
for () //枚举所有背包容量 实质就是说我要更新“当背包是v时，的最大价值”
for () //每一个组的成员
为什么要这个顺序呢，第一枚举每一个组是肯定得。至于第二层，可以这样去想。
因为最多只有一个东西进来，那么枚举背包容量的时候，实质就是说我要更新“当背包是v时，的最大价值”。然后就是更新的问题了。更新的话，就是去这个组中找一个新元素给他。一次的更新只会更新背包容量是v时的最大价值，所以不会影响后面的。
http://acm.hdu.edu.cn/showproblem.php?pid=1712
基本的分组背包。每个物品只选一次
dp[v]表示前k组中，背包容量是v时的最大价值，
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n, m; const int maxn = 1e2 + 20; int dp[maxn]; int a[maxn][maxn]; void work() { memset(dp, 0, sizeof dp); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { scanf("%d", &a[i][j]); } } for (int i = 1; i <= n; ++i) { for (int j = m; j >= 1; --j) { for (int k = 1; k <= j; ++k) { dp[j] = max(dp[j], dp[j - k] + a[i][k]); } } } printf("%d\n", dp[m]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &m) != EOF && (n + m)) work(); return 0; }
http://acm.hdu.edu.cn/showproblem.php?pid=4341
分组背包，每组物品只能取前k件。
关于斜率那里，其实是可以先按斜率排序，然后再按距离原点排序。但是一开始没想到。只会暴力对x排序，对y排序，然后每一个都暴力for一次看看有没相同的斜率，用vector保存。但是这里有x是负数的情况，要把它反转再弄。
然后就是分组背包的套路了
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n, T; const int maxn = 500 + 20; struct node { int x, y, t, val; node() {} node(int xx, int yy, int tt, int vval) : x(xx), y(yy), t(tt), val(vval) {} bool operator < (const struct node & rhs) const { if (x != rhs.x) { return x < rhs.x; } else return y < rhs.y; } }a[maxn], b[maxn]; vector<struct node>gg[maxn]; int dp[40000 + 20]; void work() { memset(dp, 0, sizeof dp); for (int i = 1; i <= maxn - 20; ++i) { gg[i].clear(); } int lena = 0, lenb = 0; for (int i = 1; i <= n; ++i) { int x, y, t, val; scanf("%d%d%d%d", &x, &y, &t, &val); if (x < 0) { b[++lenb] = node(-x, y, t, val); } else a[++lena] = node(x, y, t, val); } sort(a + 1, a + 1 + lena); sort(b + 1, b + 1 + lenb); for (int i = 1; i <= lenb; ++i) { b[i].x = -b[i].x; a[++lena] = b[i]; } assert(lena == n); int tohash = 0; for (int i = 1; i <= n; ++i) { bool flag = false; for (int j = 1; j <= tohash; ++j) { if (a[i].y * gg[j][0].x == a[i].x * gg[j][0].y) { gg[j].push_back(a[i]); flag = true; break; } } if (!flag) { gg[++tohash].push_back(a[i]); } } // cout << tohash << endl; for (int i = 1; i <= tohash; ++i) { for (int j = T; j >= 1; --j) { int sumt = 0, sumval = 0; for (int k = 0; k < gg[i].size(); ++k) { sumt += gg[i][k].t; sumval += gg[i][k].val; if (j < sumt) break; dp[j] = max(dp[j], dp[j - sumt] + sumval); } } } // printf("%d\n", dp[T]); static int f = 0; printf("Case %d: %d\n", ++f, dp[T]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &T) != EOF) work(); return 0; }
去写了个对斜率排序的，能排序，关键是y是大于0的，建议大家都写写看，代码比上面的简单不少
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> int n, T; const int maxn = 500 + 20; struct node { int x, y, t, val; node() {} node(int xx, int yy, int tt, int vval) : x(xx), y(yy), t(tt), val(vval) {} bool operator < (const struct node & rhs) const { int one = x * rhs.y; int two = rhs.x * y; if (one != two) { return one < two; } return x * x + y * y < rhs.x * rhs.x + rhs.y * rhs.y; } bool operator == (const struct node & rhs) const { return x * rhs.y == rhs.x * y; } }a[maxn]; vector<struct node>gg[maxn]; int dp[40000 + 20]; void work() { memset(dp, 0, sizeof dp); for (int i = 1; i <= maxn - 20; ++i) { gg[i].clear(); } for (int i = 1; i <= n; ++i) { scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].t, &a[i].val); } int tohash = 0; sort(a + 1, a + 1 + n); for (int i = 1; i <= n; ++i) { bool flag = false; if (tohash > 0) { if (a[i] == gg[tohash][0]) { gg[tohash].push_back(a[i]); flag = true; } } if (!flag) { gg[++tohash].push_back(a[i]); } } for (int i = 1; i <= tohash; ++i) { for (int j = T; j >= 1; --j) { int sumt = 0, sumval = 0; for (int k = 0; k < gg[i].size(); ++k) { sumt += gg[i][k].t; sumval += gg[i][k].val; if (sumt > j) break; dp[j] = max(dp[j], dp[j - sumt] + sumval); } } } static int f = 0; printf("Case %d: %d\n", ++f, dp[T]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &T) != EOF) work(); return 0; }
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326
并查集后即可
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e3 + 20; int w[maxn], val[maxn]; int fa[maxn]; int tofind(int x) { if (x == fa[x]) return x; else return fa[x] = tofind(fa[x]); } void tomerge(int x, int y) { x = tofind(x); y = tofind(y); fa[y] = x; } vector<int>gg[maxn]; bool vis[maxn]; int dp[maxn]; void work() { int n, tot, k; scanf("%d%d%d", &n, &tot, &k); for (int i = 1; i <= n; ++i) { scanf("%d%d", &val[i], &w[i]); fa[i] = i; } for (int i = 1; i <= k; ++i) { int a, b; scanf("%d%d", &a, &b); tomerge(a, b); } for (int i = 1; i <= n; ++i) { gg[tofind(i)].push_back(i); } for (int i = 1; i <= n; ++i) { if (vis[tofind(i)]) continue; vis[tofind(i)] = true; for (int j = tot; j >= 1; --j) { for (int h = 0; h < gg[tofind(i)].size(); ++h) { if (j < w[gg[tofind(i)][h]]) continue; dp[j] = max(dp[j], dp[j - w[gg[tofind(i)][h]]] + val[gg[tofind(i)][h]]); } } } cout << dp[tot] << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
背包九讲 && 题目