首页 > 代码库 > 个人专题训练——背包dp(持续更新中)

个人专题训练——背包dp(持续更新中)

 A - Proud Merchants   HDU - 3466(带限制的01背包)

题意: 给你m元,去买大米,每袋大米给你p,q,v 当你手中的钱 >= q时,才能买价格为p的这袋大米,它的价值是v,求最大价值。

01背包的转移方程根据题意很容易写出来,但是会有问题。

for (int i = 1; i <= n; ++i)
  for (int j = m; j >= q[i]; --j)
    dp[j] = max(dp[j], dp[j - p[i]] + v[i]);
考虑到了可能存在排序的问题,就按 q < 排序了,过样例,但是WA了。如果买同样的东西,肯定先买q[i]大的,才能保证还能有再买东西的可能。如何让买的东西多上加多呢,还需要买p[i]便宜的,那手中的钱减小的速度就变慢了,这样也能保证还能存在继续买东西的可能。所以最优策略应该是先买q[i] - p[i]最大的。又因为状态转移方程是逆序更新的,所以按q[i] - p[i] < 排序。

技术分享
 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 500 + 5;
 6 const int M = 5000 + 5;
 7 
 8 int n, m, dp[M];
 9 
10 struct node {
11     int p, q, v;
12 } a[N];
13 
14 bool cmp(node a, node b) {
15     return a.q - a.p < b.q - b.p;  // 关键点
16 }
17 
18 int main() {
19     while (~scanf("%d%d", &n, &m)) {
20         memset(dp, 0, sizeof(dp));
21         for (int i = 1; i <= n; ++i)
22             scanf("%d%d%d", &a[i].p, &a[i].q, &a[i].v);
23         sort(a + 1, a + n + 1, cmp);
24         for (int i = 1; i <= n; ++i)
25             for (int j = m; j >= a[i].q; --j)
26                 dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);
27         // for (int i = 1; i <= m; ++i)
28         //     printf("dp[%d]=%d%s", i, dp[i], i == m ? "\n" : " ");
29         printf("%d\n", dp[m]);
30     }
31     return 0;
32 }
View Code

C - Piggy-Bank   HDU - 1114(带限制的完全背包)

题意:给出n个硬币的价值和体积,问你能否正好装满背包,若能装满,求总价值的最小值

一般背包要求求最小值,这里初始化为INF,然后用一维的完全背包的方法直接更新就行

技术分享
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int INF = 0x3f3f3f3f;
 6 const int N = 500 + 5;
 7 const int M = 1e4 + 5;
 8 
 9 int E, F, n;
10 int dp[M], p[N], w[N];
11 
12 int main() {
13     int T; scanf("%d", &T);
14     while (T--) {
15         scanf("%d%d%d", &E, &F, &n);
16         for (int i = 1; i <= n; ++i) 
17             scanf("%d%d", &p[i], &w[i]);
18         memset(dp, INF, sizeof(dp));
19         dp[0] = 0;
20         for (int i = 1; i <= n; ++i)
21             for (int j = w[i]; j <= F - E; ++j)
22                 dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
23         if (dp[F - E] != INF)
24             printf("The minimum amount of money in the piggy-bank is %d.\n", dp[F - E]);
25         else 
26             printf("This is impossible.\n");
27     }
28     return 0;
29 }
View Code

D - I love sneakers!   HDU - 3033(分组背包变形)

背包九讲中的分组背包,是每组中最多买一件,而这道题是每组中至少买一件

技术分享

背包九讲给出的分组背包伪代码,其实就是分组的01背包。

但是这道题,需要对当前情况进行判断是否合法,必须由合法的情况更新过去。

我们考虑两种情况,当前物品是否是本组中第一次被选的,是第一次,就可以由上一组更新这一组

不是第一次,就可以组内更新,相当于组内的01背包。

还要注意初始化的问题,需要将所有不和法的情况置为-1

技术分享
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 const int M = 1e4 + 5;
 7 
 8 int dp[15][M], n, m, k;
 9 vector < pair<int, int> > vec[15];
10 
11 int main() {
12     while (~scanf("%d%d%d", &n, &m, &k)) {
13         for (int i = 0; i < 15; ++i) vec[i].clear();
14         for (int i = 1; i <= n; ++i) {
15             int a, b, c;
16             scanf("%d%d%d", &a, &b, &c);
17             vec[a].push_back(make_pair(b, c));
18         }
19         memset(dp, -1, sizeof(dp));
20         memset(dp[0], 0, sizeof(dp[0]));
21         for (int i = 1; i <= k; ++i)
22             for (int x = 0; x < (int) vec[i].size(); ++x) {
23                 int p = vec[i][x].first;
24                 for (int j = m; j >= p; --j) {
25                     int v = vec[i][x].second;
26                     if (dp[i][j - p] != -1)
27                         dp[i][j] = max(dp[i][j - p] + v, dp[i][j]);
28                     if (dp[i - 1][j - p] != -1)
29                         dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v); 
30                 }
31             }
32         if (dp[k][m] != -1)
33             printf("%d\n", dp[k][m]);
34         else 
35             printf("Impossible\n");
36     }
37     return 0;
38 }
View Code

E - AreYouBusy   HDU - 3535(混合背包)

给你n个集合,刚开始有m元。 所有数据范围都 <= 100
下面对n个集合的描述输入 x,s   表示第i个集合有x件商品,s描述该集合的性质
(s == 0:至少买一件   s == 1:至多买一件   s == 2:数量没限制)
下面x行,给出p,v    给出第i件商品的价格和价值。

思想和上面的D题差不多,因为当前组需要通过上一组的合法状态得到,或者由组内的合法状态得到

我们考虑3种情况:

技术分享

对于3种情况如何初始化也是一个问题:

对于至少买1件的,一开始本组都是不合法的,而对于其他两种情况,是站在前面的情况下更新本组的,相当于继承前一组的状态,所以要复制前一组的内容

如果用以上的方法写,还需要注意本题最坑的一点,就是存在p为0的情况。

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 const int M = 100 + 5;
 8 const int N = 100 + 5;
 9 
10 int n, m, s[N];
11 vector < pair <int, int> > vec[N];
12 int dp[N][M];
13 
14 int main() {
15     //freopen("in.txt", "r", stdin);
16     while (~scanf("%d%d", &n, &m)) {
17         for (int i = 0; i < N; ++i) vec[i].clear();
18         int x, y, p, v;
19         for (int i = 1; i <= n; ++i) {
20             scanf("%d%d", &x, &y);
21             s[i] = y;
22             while (x--) {
23                 scanf("%d%d", &p, &v);
24                 vec[i].push_back(make_pair(p, v));
25             }
26         }
27         memset(dp, 0, sizeof(dp));
28         for (int i = 1; i <= n; ++i) {
29             if (s[i]) 
30                 for (int t = 0; t <= m; ++t) dp[i][t] = dp[i - 1][t];
31             else
32                 for (int t = 0; t <= m; ++t) dp[i][t] = -1;
33             for (int x = 0; x < (int) vec[i].size(); ++x) {
34                 int p = vec[i][x].first;
35                 int v = vec[i][x].second;
36                 if (s[i] == 0) {
37                     for (int j = m; j >= p; --j) {
38                         // 下面两个if的顺序不能错,因为可能存在p为0的情况。
39                         // 如果第二个if更新成功,那么再进行第一个if,自身就合法了,就一定会再次更新,一个物品选择了两次
40                         // 注意一点:dp[i][j]自身是不合法的,需要通过合法的情况进行更新
41                         if (dp[i][j - p] != -1) 
42                             dp[i][j] = max(dp[i][j], dp[i][j - p] + v);
43                         if (dp[i - 1][j - p] != -1)
44                             dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v);
45                     }
46                 } else if (s[i] == 1) {
47                     for (int j = m; j >= p; --j) {
48                         if (dp[i - 1][j - p] != -1)
49                             dp[i][j] = max(dp[i][j], dp[i - 1][j - p] + v);
50                     }
51                 } else {
52                     for (int j = m; j >= p; --j) {
53                         if (dp[i][j - p] != -1) 
54                             dp[i][j] = max(dp[i][j], dp[i][j - p] + v);
55                     }
56                 }
57             }
58         }
59         printf("%d\n", dp[n][m]);
60     }
61     return 0;
62 }
View Code

对于本题数据范围小,而且存在p为0的情况,可以通过初始化为-INF,来直接避免考虑细节,详见代码,而且组的顺序不影响dp,代码量减少很多

技术分享
 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 100 + 5;
 6 const int INF = 0x3f3f3f3f;
 7 
 8 int n, m, s, x;
 9 int dp[N][N], p[N], v[N];
10 
11 int main() {
12     //freopen("in.txt", "r", stdin);
13     while (~scanf("%d%d", &n, &m)) {
14         memset(dp, 0, sizeof(dp));
15         for (int i = 1; i <= n; ++i) {
16             scanf("%d%d", &x, &s);
17             for (int j = 1; j <= x; ++j) scanf("%d%d", &p[j], &v[j]);
18             for (int j = 0; j <= m; ++j)
19                 dp[i][j] = s ? dp[i - 1][j] : -INF;
20             for (int k = 1; k <= x; ++k) {
21                 if (s == 0) {
22                     for (int j = m; j >= p[k]; --j)
23                         dp[i][j] = max(dp[i][j], max(dp[i][j - p[k]] + v[k], dp[i - 1][j - p[k]] + v[k]));
24                 } else if (s == 1) {
25                     for (int j = m; j >= p[k]; --j)
26                         dp[i][j] = max(dp[i][j], dp[i - 1][j - p[k]] + v[k]);
27                 } else {
28                     for (int j = m; j >= p[k]; --j)
29                         dp[i][j] = max(dp[i][j], dp[i][j - p[k]] + v[k]);
30                 }
31             }
32         }
33         printf("%d\n", max(dp[n][m], -1));
34     }
35     return 0;
36 }
View Code

F - CD   UVA - 624(记录路径的01背包)

给你n个数,和一个sum,让你找这n个数的一个序列,使得和最接近n

技术分享

参照背包九讲中的方法,这里我们用一维的01背包写,用一维是因为写了二维的时候发现,二维最后存的情况会少,所以二维的意义也只是求个maxn。

记录方法和上面讲的差不多,但是题目要求的是顺序给出选择的数。如果常规地顺序遍历数组,最后还需要从后往前逆推出答案存到vector或者数组中,

还要再逆序输出。不妨背包遍历数组的时候,就逆序遍历,就可以正推答案,也省去了存入的操作,可以直接输出。

技术分享
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int M = 1e4 + 5;
 6 
 7 int dp[M], vis[25][M];
 8 int a[25], n, m;
 9 
10 int main() {
11     freopen("in.txt", "r", stdin);
12     while (~scanf("%d%d", &n, &m)) {
13         for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
14         memset(dp, 0, sizeof(dp));
15         memset(vis, 0, sizeof(vis));
16         for (int i = m; i >= 1; --i)
17             for (int j = n; j >= a[i]; --j) {
18                 dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
19                 if (dp[j] == dp[j - a[i]] + a[i])
20                     vis[i][j] = 1;
21             }
22         int j = n;
23         for (int i = 1; i <= m; ++i)
24             if (vis[i][j]) {
25                 printf("%d ", a[i]);
26                 j -= a[i];
27             }
28         printf("sum:%d\n", dp[n]);
29     }
30     return 0;
31 }
View Code

G - Dividing coins   UVA - 562(转化成01背包)

给你n个数,让你把它分成两堆,使得两堆的和之差尽量小,求这个差值。

换个说法就是,既然可以分成两堆,那么就是找存在和为sum的方案数,以及和为n - sum的方案数也存在的情况,使abs(2 * sum - n)尽量小

背包九讲中说:直接把01背包那里的max改为sum就行,因为已经遍历了所有可能的组成情况。这样题目就很简单了。dp[i] 表示和为 i 的方案数。

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 const int N = 100 + 5;
 7 const int M = 5e4 + 5;
 8 
 9 int a[N];
10 int dp[M];
11 
12 int main() {
13     int t; scanf("%d", &t);
14     while (t--) {
15         int n; scanf("%d", &n);
16         int sum = 0;
17         for (int i = 1; i <= n; ++i) {
18             scanf("%d", &a[i]);
19             sum += a[i];
20         }
21         memset(dp, 0, sizeof(dp));
22         dp[0] = 1;
23         for (int i = 1; i <= n; ++i) 
24             for (int j = sum; j >= a[i]; --j)
25                 dp[j] += dp[j - a[i]];
26         int ans = sum;
27         for (int i = 1; i <= sum; ++i)
28             if (dp[i] && dp[sum - i])
29                 ans = min(ans, abs(sum - i * 2));
30         printf("%d\n", ans);
31     }
32     
View Code

H - Dollars   UVA - 147(转化成完全背包)

给你很多种面值的硬币,让你求构成面值和为sum的方案数,硬币数量不限制

和G题基本一样,就是把换成完全背包的写法,状态转移方程不变。还有一个坑点,就是浮点数转化成整数有误差。

技术分享
 1 /*
 2  double 保证小数点后15位准确
 3  坑点:  18.90 * 100 = 1889 (精度误差得可怕)
 4  无误差的方法(一般不用):
 5      (tmp * 1000 - tmp * 100) / 9;
 6  更常用的方法:
 7       (tmp + eps) * 100    eps足够小
 8 */
 9 #include <cstdio>
10 #include <cstring>
11 using namespace std;
12 const double eps = 1e-6;
13 const int M = 3e4 + 5;
14 
15 int m;
16 long long dp[M];
17 int a[11] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};
18 
19 void init() {
20     dp[0] = 1;
21     for (int i = 0; i < 11; ++i)
22         for (int j = a[i]; j <= 30000; ++j)
23             dp[j] += dp[j - a[i]];
24 }
25 
26 int main() {
27     init();
28     double tmp;
29     while (~scanf("%lf", &tmp) && tmp) {
30         m = (tmp + eps) * 100;
31         printf("%6.2lf%17lld\n", tmp, dp[m]);
32     }
33     return 0;
34 }
View Code

 

 

个人专题训练——背包dp(持续更新中)