背包问题系列（01背包、完全背包、多重背包）

背包问题是一个经典的动态规划问题，问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。根据给定物品的数量，背包问题又可分为：

1）每种物品只有一件，即01背包问题

2）每种物品不限数量，可选取任意数量，即完全背包问题

3）每种物品的数量已给定，不可超出该数量，即多重背包问题

背包问题的重点：

1）编写状态转移方程

2）空间优化

本文参考https://zhuanlan.zhihu.com/p/93857890，使用C++代码完成了三种问题的代码及空间优化代码

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 int max(int a, int b)
  6 {
  7     return a > b ? a : b;
  8 }
  9 
 10 int min(int a, int b)
 11 {
 12     return a < b ? a : b;
 13 }
 14 
 15 // 01背包问题,n件物品，重量为v
 16 int BagProblem_01(const vector<int> &weight, const vector<int> &value, int n, int v)
 17 {
 18     // 前i件物品背包限重为j的情况下的最大值
 19     vector<vector<int>> dp(n, vector<int>(v + 1, 0));
 20 
 21     for (int i = 0; i <= v; i++)
 22     {
 23         if (i >= weight[0])
 24         {
 25             dp[0][i] = value[0];
 26         }
 27     }
 28 
 29     for (int i = 1; i < n; i++)
 30     {
 31         for (int j = 1; j <= v; j++)
 32         {
 33             if (j < weight[i])
 34             {
 35                 dp[i][j] = dp[i - 1][j];
 36             }
 37             else
 38             {
 39                 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
 40             }
 41         }
 42     }
 43 
 44     return dp[n - 1][v];
 45 }
 46 
 47 // 01背包问题--优化空间
 48 int BagProblem_01_optimize(const vector<int> &weight, const vector<int> &value, int n, int v)
 49 {
 50     // 前i件物品背包限重为j的情况下的最大值
 51     vector<int> dp(v + 1, 0);
 52 
 53     for (int i = 0; i <= v; i++)
 54     {
 55         if (weight[0] > v)
 56         {
 57             dp[0] = value[0];
 58         }
 59     }
 60 
 61     for (int i = 1; i < n; i++)
 62     {
 63         for (int j = v; j >= weight[i]; j--)    // dp[j]是由上一行<=j列推出，j需逆向枚举
 64         {
 65             dp[j] = max(dp[j], dp [j - weight[i]] + value[i]);
 66         }
 67     }
 68 
 69     return dp[v];
 70 }
 71 
 72 // 完全背包问题
 73 int BagProblem_complete(const vector<int> &weight, const vector<int> &value, int n, int v)
 74 {
 75     vector<vector<int>> dp(n, vector<int>(v + 1, 0));
 76 
 77     for (int j = 0; j <= v; j++)
 78     {
 79         dp[0][j] = j / weight[0] * value[0];
 80     }
 81 
 82     for (int i = 1; i < n; i++)
 83     {
 84         for (int j = 0; j <= v; j++)
 85         {
 86             if (j < weight[i])
 87             {
 88                 dp[i][j] = dp[i - 1][j];
 89             }
 90             else
 91             {
 92                 dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
 93             }
 94         }
 95     }
 96 
 97     return dp[n - 1][v];
 98 }
 99 
100 // 完全背包问题——优化空间
101 int BagProblem_complete_optimize(const vector<int> &weight, const vector<int> &value, int n, int v)
102 {
103     vector<int> dp(v + 1, 0);
104 
105     for (int j = 0; j <= v; j++)
106     {
107         dp[j] = j / weight[0] * value[0];
108     }
109 
110     for (int i = 1; i < n; i++)
111     {
112         for (int j = 0; j <= v; j++)    // dp[j]是由上一行j列和本行小于j列推出，因此需要正向枚举
113         {
114             if (j >= weight[i])
115             {
116                 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
117             }
118         }
119     }
120 
121     return dp[v];
122 }
123 
124 // 多重背包问题
125 int BagProblem_multi(const vector<int> &weight, const vector<int> &value, const vector<int> &nums, int n, int v)
126 {
127     vector<vector<int>> dp(n, vector<int>(v + 1, 0));
128 
129     for (int j = 0; j <= v; j++)
130     {
131         int num = min(j / weight[0], nums[0]);
132         dp[0][j] = num * value[0];
133     }
134 
135     for (int i = 1; i < n; i++)
136     {
137         for (int j = 0; j <= v; j++)
138         {
139             if (j < weight[i])
140             {
141                 dp[i][j] = dp[i - 1][j];
142             }
143             else
144             {
145                 int num = min(j / weight[i], nums[i]);
146                 for (int k = 0; k <= num; k++)
147                 {
148                     dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - k * weight[i]] + k * value[i]);
149                 }
150             }
151         }
152     }
153 
154     return dp[n - 1][v];
155 }
156 
157 // 多重背包问题——优化空间
158 int BagProblem_multi_optimize(const vector<int> &weight, const vector<int> &value, const vector<int> &nums, int n, int v)
159 {
160     vector<int> dp(v + 1, 0);
161 
162     for (int j = 0; j <= v; j++)
163     {
164         int num = min(j / weight[0], nums[0]);
165         dp[j] = num * value[0];
166     }
167 
168     for (int i = 1; i < n; i++)
169     {
170         for (int j = v; j >= 0; j--)    // dp[j]是由上一行<=j列推出，需要逆向枚举
171         {
172             int num = min(j / weight[i], nums[i]);
173             for (int k = 0; k <= num; k++)
174             {
175                 if (j < k * weight[i])
176                     continue;
177                 dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
178             }
179         }
180     }
181 
182     return dp[v];
183 }
184 
185 int main()
186 {
187     int v = 10;
188     int n = 5;
189     vector<int> weight{ 2, 2, 4, 6, 3 };
190     vector<int> value { 1, 3, 3, 5, 6 };
191     vector<int> nums  { 1, 2, 3, 4, 1 };
192 
193     cout << BagProblem_01(weight, value, n, v) << endl;
194     cout << BagProblem_01_optimize(weight, value, n, v) << endl;
195 
196     cout << BagProblem_complete(weight, value, n, v) << endl;
197     cout << BagProblem_complete_optimize(weight, value, n, v) << endl;
198 
199     cout << BagProblem_multi(weight, value, nums, n, v) << endl;
200     cout << BagProblem_multi_optimize (weight, value, nums, n, v) << endl;
201 
202     return 0;
203 }