背包九讲

798236606

测试平台：https://www.acwing.com/problem/

1.01背包

解：

二维DP

dp[j]表示前i个物品在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp[0]必须初始化为0（因为前0个物品的价值量肯定为0）

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int maxn = 1e3 + 10;
   
7. 
   
8. int n, m;
   
9. int dp[maxn][maxn];
   
10. 
    
11. int main(void)
    
12. {
    
13.     cin >> n >> m;
    
14.    
    
15.     for (int i = 1; i <= n; ++i)
    
16.     {
    
17.         int v, w;
    
18.         
    
19.         cin >> v >> w;
    
20.         
    
21.         for (int j = 0; j <= m; ++j)//如果装不下，则继承i - 1的结果,若装的下则考虑装与不装哪个更赚
    
22.             dp[i][j] = (j < v) ? dp[i - 1][j] : max(dp[i - 1][j], dp[i - 1][j - v] + w);
    
23.     }
    
24.    
    
25.     cout << dp[n][m] << endl;
    
26. 
    
27.     return 0;
    
28. }

复制代码

【注】大多数一维DP做起来很困难，此时升到二维会简单很多

一维DP

dp[j]表示当前物品与之前的物品（其实还是前i个物品）在剩余空间为j的情况下能够装的最大价值量（不一定恰好装满），其中dp必须初始化为0（因为前0个物品的价值量肯定为0）

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int maxn = 1e3 + 10;
   
7. 
   
8. int n, m;
   
9. int dp[maxn];
   
10. 
    
11. int main(void)
    
12. {
    
13.     cin >> n >> m;
    
14.    
    
15.     while (n--)
    
16.     {
    
17.         int v, w;
    
18.         
    
19.         cin >> v >> w;
    
20. 
    
21.         //装不下的情况不用管，会自然地继承上一次的计算结果，每次计算只是对上次计算的加工处理。j从后往前保证每个物品只被计算一次
    
22.         for (int j = m; j >= v; --j) dp[j] = max(dp[j], dp[j - v] + w);
    
23.     }
    
24.    
    
25.     cout << dp[m] << endl;
    
26. 
    
27.     return 0;
    
28. }

复制代码

2.完全背包

解：

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int maxn = 1e3 + 10;
   
7. 
   
8. int n, m;
   
9. int dp[maxn];
   
10. 
    
11. int main(void)
    
12. {
    
13.     cin >> n >> m;
    
14.    
    
15.     while (n--)
    
16.     {
    
17.         int v, w;
    
18.         
    
19.         cin >> v >> w;
    
20. 
    
21.         //j从前往后保证每个物品可以被计算多次
    
22.         for (int j = v; j <= m; ++j) dp[j] = max(dp[j], dp[j - v] + w);
    
23.     }
    
24.    
    
25.     cout << dp[m] << endl;
    
26. 
    
27.     return 0;
    
28. }

复制代码

其实还有一种更容易想到的解法：枚举每件物品的选取个数（其实把问题转化成了01背包）

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int maxn = 1e3 + 10;
   
7. 
   
8. int n, m;
   
9. int dp[maxn];
   
10. 
    
11. int main(void)
    
12. {
    
13.     cin >> n >> m;
    
14.    
    
15.     while (n--)
    
16.     {
    
17.         int v, w;
    
18.         
    
19.         cin >> v >> w;
    
20. 
    
21.         for (int j = m; j >= v; --j)
    
22.             for (int k = 1; k * v <= j; ++k)
    
23.                 dp[j] = max(dp[j], dp[j - k * v] + k * w);
    
24.     }
    
25.    
    
26.     cout << dp[m] << endl;
    
27. 
    
28.     return 0;
    
29. }

复制代码

3.多重背包Ⅰ

解:

类似于上一题的第二种解法

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. const int maxn = 1e2 + 10;
   
7. 
   
8. int n, m;
   
9. int dp[maxn];
   
10. 
    
11. int main(void)
    
12. {
    
13.     cin >> n >> m;
    
14.    
    
15.     while (n--)
    
16.     {
    
17.         int v, w, t;
    
18.         
    
19.         cin >> v >> w >> t;
    
20. 
    
21.         for (int j = m; j >= v; --j)
    
22.             for (int k = 1; k <= t && k * v <= j; ++k)
    
23.                 dp[j] = max(dp[j], dp[j - k * v] + k * w);
    
24.     }
    
25.    
    
26.     cout << dp[m] << endl;
    
27. 
    
28.     return 0;
    
29. }

复制代码

但是当数据较大时效率就会比较差，此时使用二进制优化法

4.多重背包Ⅱ

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int maxn = 2e3 + 5;
   
8. 
   
9. typedef struct GOOD{
   
10.     int v, w;
    
11.    
    
12.     GOOD (int _v, int _w) : v(_v), w(_w) {};
    
13. }Good;
    
14. 
    
15. int n, m;
    
16. int dp[maxn];
    
17. vector<Good> goods;
    
18. 
    
19. int main(void)
    
20. {
    
21.     cin >> n >> m;
    
22.    
    
23.     while (n--)
    
24.     {
    
25.         int v, w, t;
    
26.         
    
27.         cin >> v >> w >> t;
    
28.         
    
29.         for (int k = 1; k <= t; t -= k, k *= 2)
    
30.             goods.push_back(GOOD(k * v, k * w));
    
31.             
    
32.         if (t) goods.push_back(GOOD(t * v, t * w));
    
33.     }
    
34.    
    
35.     for (auto good: goods)
    
36.         for (int j = m; j >= good.v; --j)
    
37.             dp[j] = max(dp[j], dp[j - good.v] + good.w);
    
38.    
    
39.     cout << dp[m] << endl;
    
40.    
    
41.     return 0;
    
42. }

复制代码

未完待续。。。

ming@1993

多谢！