背包系列问题常采用的方法为
动态规划
。背包系列可分为01背包、完全背包、多重背包。
一、01背包
01背包含义
：现有N个重量是weight[i]，价值value[i]物品，而背包的容量为bagweight，设问在任取物品放进背包后，背包的最大价值为多少？（
注意：每一个物品只能选一次或不选，也是01背包叫法的来源
）
思路：采用动态规划
dp[i][j]的含义
：表示容量j的背包选取第i个物品后，背包的最大价值为dp[i][j]。
确定dp方程
：
dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-weight[i]] + value[i]);
，当背包的容量j<weight[i]时，无法选取第i个物品，故dp[i][j]=dp[i-1][j]；当背包容量j>=weight[i]时，可以选取当前的物品，则dp[i][j]=dp[i-1][j-weight[j]]+value[i]，也可以不选，则dp[i][j]=dp[i-1][j]。
分析如何初始化dp
：根据dp方程可知，dp[i]是由dp[i-1]推导得出的，故dp[0][j]必须初始化，dp[0][j]表示选取第0个物品后背包容量j的价值为多少，很显然是j>=weight[0]情况下，dp[0][j]=value[0]。
遍历顺序
：由dp[i][j]定义可知，二维数组需要两层的for循环，那到底是先遍历i还是先遍历j呢？由dp方程可看出，不管是dp[i]还是dp[i][j]都是由二维数组的左上角推导出来的，而我们在之前已经初始化了dp，故遍历顺序俩者都可行。
完整代码：
//二维的01背包
void test_01Bag_Fun()
{
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
//dp[i][j]表示任意选取第i个物品后放进容量为j的背包里，获取最大价值
vector<vector<int>> dp(weight.size(), vector<int>(bagweight+1, 0));
//初始化dp[0]
for (int i = weight[0];i <= bagweight;i++)
dp[0][i] = value[0];
//dp方程 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
//当容量j的背包不能放进weight[i]时，那么dp[i][j]=dp[i-1][j]，后者则时放进背包
//推导出：要获取dp[i][j]之前，必须知道dp[i-1][j]，故需要初始化dp[0]
//遍历顺序：先物品，再重量 或 先重量，再物品都可以
for (int i = 1;i < weight.size();i++)
{
for (int j = weight[i];j <= bagweight;j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout << "bag max value = " << dp[weight.size() - 1][bagweight] << endl;
}
对于二维的背包还可以进一步优化成一维的背包。
优化思想：
从二维的dp方程出发
：dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])，我们可以将dp[i-1]加入到dp[j]中，就变成了一维数组的dp[j]。
回想一下刚才讲解的二维dp[i][j]的含义，指背包容量j可以选取任意物品放入，得到的最大价值。
而一维dp[j]的含义：背包容量j可以放进任意物品，所获取的最大价值。
dp方程
：
dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
，意思时当j>=weight[i]时，dp[j]=dp[j]（不选）,或dp[j]=dp[j-weight[i]]+value[i]（选）；当j<weight[i]时，无法放入背包，则dp[j]=dp[j]。
dp初始化
：一维的dp的初始化和二维dp不同，由dp方程可知，dp[j]是由dp[j-weight[i]]推导出的，故需要初始化dp[0]，而dp[0]表示背包的重量为0，那么dp[0]=0；
需要注意的是，当背包选择不放进物品时，dp[j]=dp[j]，所以需要初始化dp[j]=0，才能不影响选取后的背包价值。
遍历顺序
：这里格外的注意一下，和二维的遍历方式不同，一维的dp只能
先遍历物品，再遍历背包重量且从后开始
，因为物品只能放入背包一次或不放。而为什么二维的遍历顺序是任意的呢，因为二维的dp[i][j]中的dp[i]已经表示了放入第i件物品了。
完整代码
:
//一维的01背包
void test_01Bag_Fun2()
{
vector<int> weight = { 1, 3, 4 };
vector<int> value = { 15, 20, 30 };
int bagweight = 4;
//dp[j]表示 容量j的背包装进物品后的最大价值
vector<int> dp(bagweight + 1, 0);
//dp方程，dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
for (int i = 0;i < weight.size();i++)
{
//从后开始，避免了物品多次被放进背包
//例如：从前面开始：dp[1]=dp[1-1]+15=15，dp[2]=dp[2-1]+15=30（再次将weight[0]放进背包）;
//两次都将weight[0]放进背包，故需要从后遍历避免该问题
//从后面开始：dp[4]=dp[4-1]+15=15，dp[3]=dp[3-1]+15=15;
for (int j = bagweight;j >= weight[i];j--)
{
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << "bag max value = " << dp[bagweight] << endl;
}
二、完全背包
有了01背包的基础之后，我们可以进一步了解什么是完全背包。
完全背包的含义：在01背包的定义中，我提及了需要注意的点是每个物品只能放进一次或不放，这就是0和1意思，那么完全背包是每个物品可以放无限次。
限制条件
：可能有的博友疑惑说，物品可以无限制的放入，那是不是没有约束条件了。那倒不会，或许你没注意到背包的容量是有限制的，不信回头看一看01背包的讲解，对于完全背包来说，约束条件是背包的容量。
dp[j]的定义
：表示背包容量为j放入物品后的最大价值
dp方程
：
dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
，意思时当j>=weight[i]时，dp[j]=dp[j]（不选）,或dp[j]=dp[j-weight[i]]+value[i]（选）；当j<weight[i]时，无法放入背包，则dp[j]=dp[j]。
dp初始化
：由dp方程可知，dp[j]是由dp[j-weight[i]]推导出的，故需要初始化dp[j]；
遍历方式
：由于完全背包放入的物品可以是重复的，所以内层的for循环只能是物品。
完整代码
：
//完全背包
/*
有n种物品，每种物品的单件重量为w[i]，价值为c[i]。
现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。
注意：其中每种物品都有无穷件。
*/
void test_Bag_Fun3()
{
vector<int> weight = { 1, 2, 3 };
vector<int> value = { 15, 20, 50 };
int bagweight = 4;
vector<int> dp(bagweight+1, INT_MIN+1);
dp[0] = 0;
for (int j = 1;j <= bagweight;j++)
{
for (int i = 0;i < weight.size();i++)
{
if (j >= weight[i])
dp[j] = max(dp[j], dp[j - weight[i]]+value[i]);
}
}
cout << "bag max value = " << dp[bagweight] << endl;
}
三、多重背包
题目描述
：
有n种物品，每种物品的单件重量为w[i]，价值为c[i]。
现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。
注意：其中每种物品最多能放入nums[i]。
//多重背包
/*
有n种物品，每种物品的单件重量为w[i]，价值为c[i]。
现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。
注意：其中每种物品最多能放入nums[i]。
*/
//二维的多重背包
void test_Bag_Fun4()
{
vector<int> weight = { 1, 2, 3 };
vector<int> value = { 15, 20, 50 };
//每种物品最多能放入的次数
vector<int> nums = { 2, 3, 4 };
int bagweight = 8;
vector<int> dp(bagweight + 1, 0);
for (int i = 0;i < weight.size();i++)
{
for (int j = bagweight;j >= weight[i];j--)
{
for (int k = 0;k <= nums[i] && k*weight[i] <= j;k++)
{
dp[j] = max(dp[j], dp[j - k*weight[i]] + k*value[i]);
}
}
}
cout << "bag max value = " << dp[bagweight] << endl;
}
//优化版的多重背包
//01背包
void zeroOnePackCore(vector<int> &F, int c, int w, int V) {
for (int v = V;v >= c;v--) {
F[v] = max(F[v], F[v - c] + w);
}
}
//完全背包
void completePackCore(vector<int> &F, int c, int w, int V) {
for (int v = c;v <= V;v++) {
F[v] = max(F[v], F[v - c] + w);
}
}
void multiplePackCore(vector<int> &F, int c, int w, int m, int V) {
if (c * m >= V) {
completePackCore(F, c, w, V);
return;
}
int k = 1;
while (k < m) {
zeroOnePackCore(F, c*k, w*k, V);
m = m - k;
k = k * 2;
}
zeroOnePackCore(F, c*m, w*m, V);
}
void multiplePackOptimize() {
vector<int> weight = { 1, 2, 3 };
vector<int> value = { 15, 20, 50 };
//每种物品最多能放入的次数
vector<int> nums = { 2, 3, 4 };
int bagweight = 8;
vector<int> dp(bagweight + 1, 0);
for (int i = 1;i<weight.size() + 1;i++) {
multiplePackCore(dp, weight[i - 1], value[i - 1], nums[i - 1], bagweight);
}
cout << "bag max value = " << dp[bagweight] << endl;
}
如何对多重背包的物品选择进行输出查看呢？普通的思路一般采用二维的多重背包dp，使用三维的res数组标记物品的使用情况。
void test_Bag_Fun4()
{
vector<int> weight = {0, 1, 2, 3 };
vector<int> value = {0, 15, 20, 50 };
//每种物品最多能放入的次数
vector<int> nums = {0, 2, 3, 4 };
int bagweight = 8;
//标记物品的选择状态
vector<vector<vector<int>>> res(weight.size(), vector<vector<int>>(bagweight + 1, vector<int>(weight.size(), 0)));
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int i = 1;i < weight.size();i++)
{
for (int j = weight[i];j <= bagweight;j++)
{
for (int k = 0;k <= nums[i] && k*weight[i] <= j;k++)
{
//更新物品被选择后的状态
if (dp[i - 1][j] < dp[i - 1][j - k*weight[i]] + k*value[i])
{
res[i][j] = res[i - 1][j - k*weight[i]];
res[i][j][i] = k;
}
else
res[i][j] = res[i - 1][j];
dp[i][j] = max(dp[i-1][j], dp[i-1][j - k*weight[i]] + k*value[i]);
}
}
}
for (int i = 1;i < nums.size();i++)
{
if (res[nums.size() - 1][bagweight][i] == 0) continue;
cout << "i = " << i << " " << res[nums.size() - 1][bagweight][i] << endl;
}
cout << "bag max value = " << dp[weight.size()-1][bagweight] << endl;
}