目录
一、01背包问题
二、完全背包问题
三、多重背包
问题：
有n件物品和一个容量是m的背包。第i件物品的体积是vi，价值是wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
解答：
问题中每个物品只有选与不选两种状态。
动态规划的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-vi]+wi) , d[i][j]表示只看前i个物品且总体积是j时，最大的价值。
//v是物品的体积，w是价值，m是背包容量 int package(vector<int> &v, vector<int> &w, int m) { int n = v.size(); vector<vector<int>> dp(n+1, vector<int>(m+1,0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j]; if(j >= v[i-1]) dp[i][j] = max(dp[i][j], dp[i-1][j - v[i-1]] + w[i-1]); } } return dp[n][m]; }代码分析：
首先，最外层遍历物品（1~n）。内层遍历背包容量（1~m）。在实现dp[i][j] = max(dp[i-1][j], dp[i][j-vi]+wi)状态转移时，在计算dp[i][j]时，需要使用dp[i-1][j]的内容。观察代码可以发现每次的状态转移只与上一次的结果有关，会使dp[i-1][j] 与dp[i-1][j-vi]。
我们反向使用上一次的结果可以简化辅助空间得到下面的状态转移：dp[j] = max(dp[j], dp[j-vi]+wi)
int package(vector<int> &v, vector<int> &w, int m) { int n = v.size(); vector<int> dp(m + 1, 0); for (int i = 0; i < n; i++) { for (int j = m; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } return dp[m]; }
问题：
有n种物品，每种物品可以选无数次和0次，背包的容量是m。第i件物品的体积是vi，价值是wi。 求：将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
分析：
问题中每个物品拥有选择多个和不选的状态。
动态规划的状态转移方程与01背包相同：dp[j] = max(dp[j], dp[j-vi]+wi) , d[j]表示总体积是j时，最大的价值。
int package(vector<int> &v, vector<int> &w, int m) { int n = v.size(); vector<int> dp(m + 1, 0); for (int i = 0; i < n; i++) { for (int j = v[i]; j <= m; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } return dp[m]; }与01背包问题的代码略微有点不同，最外层同样是遍历物品（1~n）。内层遍历从v[i]开始到m
问题：
有n种物品和一个容量是m的背包。第i种物品的体积是vi，价值是wi,数量是si 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
可以把多重背包看作是01背包处理，使用与01背包相同的方法。
int package(vector<int> &v, vector<int> &w, vector<int> &s, int m) { int n = v.size(); vector<int> dp(m + 1, 0); for (int i = 0; i < n; i++) { for (int j = m; j >= v[i]; j--) { for (int k = 1; k <= s[i] && k*v[i] <= j; k++) { dp[j] = max(dp[j], dp[j - k*v[i]] + k*w[i]); } } } return dp[m]; }代码分析：
与01背包同样的方法 ，只是把每一个物品的不同数量si当做是有si种物品进行处理，多了一层对同一物品的循环。
时间复杂度O（n3）
二进制优化的方法
学过linux操作系统的同学应该知道，修改linux文件的权限的数字法。
如何使用最少的数的组合表示一个数的全域。比如：用一些数字或它们的组合来表示（1~7）所有的数。
0 0 0 4 2 1在二进制中，7 = 4+2+1，6=4+2，5=4+1，4=4，3=2+1，2=2，1=1
在上一个方法中，我们需要遍历同一物品的所有的个数。复杂度很高，使用二进制方法可以，有效降低时间复杂度。
比如有一种物品i有si件，如果si是7时。我们可以把这些物品拆分成4件，2件，1件。将4件物品的体积与价值分别相加当作一件新的物品加入物品集合，接下来2件，1件同理。我们就得到了一个每种物品只有1件的物品集合。可以用01背包方法来解决。
int package_bit(vector<int> &v, vector<int> &w, vector<int> s, int m) { int n = v.size(); vector<int> vr, wr; for (int i = 0; i < n; i++) { for (int k = 1; k <= s[i]; k *= 2) { s[i] -= k; vr.emplace_back(k*v[i]); wr.emplace_back(k*w[i]); } if (s[i] > 0) { vr.emplace_back(s[i] * v[i]); wr.emplace_back(s[i] * w[i]); } } vector<int> dp(m + 1, 0); for (int i = 0; i < vr.size(); i++) { for (int j = m; j >= vr[i]; j--) { dp[j] = max(dp[j], dp[j - vr[i]] +wr[i]); } } return dp[m]; }
