动态规划入门-完全背包
问题描述
一共有 N 种物品，每种物品都有无数个，第 i （i 从 0 开始）种物品的重量为 w[i]，价值为 v[i] 。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？
暴力递归-每种都尝试
与之前的 01背包问题 不同，N 件物品变成了 N 种物品，且每种物品的数量不限。由于每种物品可以取多次，所以这类问题并不好用“从左到右、要或不要”模型来解决。 更自然的解法是在每层递归中对所有物品都尝试取一次，然后返回所有情况中最大的值。
也可以使用“从左到右、要或不要”的模型，只是有一定限制，见后文。
int knapSackUnlimited(vector<int> weight, vector<int> value, int capacity)
{
if(capacity < 0)
return 0;
int maxVal = 0;
for(int i = 0; i < weight.size(); i++)
{
int val = 0;
if(weight[i] <= capacity)//容易忽略
val = value[i] + knapSackUnlimited(weight, value, capacity - weight[i]);
maxVal = maxVal > val ? maxVal : val;
}
return maxVal;
}
显然在递归中有枚举行为（for循环），对每一种物品都尝试取一次，然后比较各自的值，最后返回最大值。
注意第 9 行的判断容易忽略，只有当 capacity 足够装下本次选择的物品时，才可以取该物品，否则 maxVal 不变。
另外，因为有了第 9 行的判断，第 3、4 行的基线条件事实上就可以省略，但为了防止 capacity 小于 0 时还进行无意义的枚举，还是最好加上。下面我们将其改进为动态规划。
动态规划1
int knapSackUnlimited(vector<int> weight, vector<int> value, int capacity)
{
vector<int> dp(capacity + 1, 0);
for(int c = 0; c <= capacity; c++)
{
int maxVal = 0;
for(int i = 0; i < weight.size(); i++)
{
int val = 0;
if(weight[i] <= c)
val = value[i] + dp[c - weight[i]];
maxVal = maxVal > val ? maxVal : val;
}
dp[c] = maxVal;
}
return dp[capacity];
}
此动态规划甚至不需要特例初始化，第 6~14 行几乎完全同暴力递归代码。
暴力递归-从左到右
int process(vector<int> weight, vector<int> value, int index, int capacity)
{
if(index >= weight.size() || capacity < 0)
return 0;
int ret1 = process(weight, value, index + 1, capacity);//不要此货物
int ret2 = 0;
if(weight[index] <= capacity)//当前容量够,才能要此货物
ret2 = value[index] + process(weight, value, index, capacity - weight[index]);//要此货物
return std::max(ret1 , ret2);
}
int knapSackUnlimited1(vector<int> weight, vector<int> value, int capacity)
{
if(weight.size() != value.size())
return 0;
return process(weight, value, 0, capacity);
}
对比一下 01背包 的代码：
int process(const vector<int> &weight, const vector<int> &value, int index, int capacity)
{
if(index >= weight.size() || capacity < 0)//capacity可以为0
return 0;
int ret1 = process(weight, value, index + 1, capacity);//不要此货物
int ret2 = 0;
if(weight[index] <= capacity)//当前容量够,才能要此货物
ret2 = value[index] + process(weight, value, index + 1, capacity - weight[index]);//要此货物
return std::max(ret1 , ret2);
}
int knapSack(vector<int> weight, vector<int> value, int capacity)
{
if(weight.size() != value.size())
return 0;
return process(weight, value, 0, capacity);
}
惊人地发现，这两种问题的代码仅有一处不同，即第 8 行的 index 实参是否加 1 。
前者的 index 实参不加 1 是因为：当你选择该种商品后，下一次你仍然可以继续选择该商品。 这种方法和前面的“每种都尝试”方法所达到的效果是一致的。
动态规划2
int knapSackUnlimited3(vector<int> weight, vector<int> value, int capacity)
{
vector<vector<int>> dp(weight.size(), vector<int>(capacity + 1, 0));
int last = weight.size() - 1;
//特例初始化
for(int c = 0; c <= capacity; c++)
{
if(weight[last] <= c)
dp[last][c] = value[last];
}
//依次打表
for(int i = weight.size() - 2; i >= 0; i--)
{
for(int c = 0; c <= capacity; c++)
{
int ret1 = dp[i+1][c];
int ret2 = 0;
if(weight[i] <= c)
ret2 = value[i] + dp[i][c-weight[i]];
dp[i][c] = std::max(ret1, ret2);
}
}
return dp[0][capacity];
}
由暴力递归中的递推表达式可知，当前 index 依赖于 index + 1，所以打表必须按 index 从后往前进行 ，故外层 for 循环从 weight.size()-2 开始；capacity 则是后面依赖前面的，所以打表必须按 capacity 从前往后打，故内层 for 循环是从 c = 0 开始的。
补充
博主后来发现上述的“每种都尝试”模型并不是完全背包题型的通解。上面的暴力递归中其实存在重复解，比如下面情况：
第 1 次取 ① 号货物；
第 2 次取 ② 号货物；
第 3 次取 ① 号货物；结束
即取了 1 个 ② 号货物和 2 个 ① 号货物，再看下面这种情况：
第 1 次取 ① 号货物；
第 2 次取 ① 号货物；
第 3 次取 ② 号货物；结束
也是取了 1 个 ② 号货物和 2 个 ① 号货物。这两种情况是相同的，所以返回的最大值也相同。而由于题目要求的是返回所有情况中的最大价值，所以这两者返回谁都无所谓，答案依然正确。
但如果将题目修改为：要求背包必须恰好装满总价值为 K 的货物，一共有多少种装法？那结果就不一样了。假设 1 个 ② 号货物和 2 个 ① 号货物的总价值刚好为 K ，则上面的两种情况实际上只能算作一种取法，而非两种 ，只是取得货物的顺序不同而已。
综上，如果完全背包类型的题目要求取最值，则可以不去重；如果要求取方法数，则必须去重 。
本题去重版本的暴力递归代码如下：
int knapSackUnlimited4(vector<int> weight, vector<int> value, int capacity, int index)
{
if(capacity < 0 || index >= weight.size())//capacity<0可以省去
return 0;
int max = 0;
for(int i = 0; i * weight[index] <= capacity; i++)
{
int ret = knapSackUnlimited4(weight, value, capacity - weight[index] * i, index + 1);
max = max > (i * value[index] + ret) ? max : (i * value[index] + ret);
}
return max;
}
上面代码的思想是：集中处理每种物品的所有取法 ，比如 ① 号物品在 不超过 capacity 的情况下 可以分别只取 1 次、2 次、3 次…取完后继续统计 ② 号物品的取法，② 号物品在 不超过 capacity(取完①号货物后) 的情况下 也只取 1 次、2 次、3 次…这样就不会出现重复情况。动态规划代码如下：
int knapSackUnlimited(vector<int> weight, vector<int> value, int capacity)
{
vector<vector<int>> dp(capacity + 1, vector<int>(weight.size(), 0));
for(int c = 0; c <= capacity; c++)//从上往下填表
{
for(int index = weight.size() - 1; index >= 0; index--)//从右往左填表
{
int max = 0;
for(int i = 0; i * weight[index] <= c; i++)
{
int ret = index+1 > weight.size() ? 0 : dp[c-weight[index]*i][index+1];
max = max > (i * value[index] + ret) ? max : (i * value[index] + ret);
}
dp[c][index] = max;
}
}
return dp[capacity][0];
}
由于每个格子依赖的是右上方的格子，所以填表时需要从上到下，从右到左进行。
那么如果要求背包必须恰好装满总价值为 K 的货物，一共有多少种装法呢？这个问题参见动态规划-硬币系列2。
总结
-
完全背包可以选择“从左到右”模型，也可以选择“每一种都尝试”模型。但前者在某些时候会有一定限制，具体参见杀死那只怪兽、贴纸拼词。
-
完全背包类型的题目如果要求取最值，则可以不去重；如果要求取方法数，则必须去重。
-
实际上，就暴力递归而言，“从左到右”模型远优于“每一种都尝试模型”，因为前者的递归分支仅有两个，而后者则可能达数十个（for循环）。要知道递归分支可比单纯的 for 循环带来的的时间消耗要大得多！ 我们写一个测试代码就能够看出差别：
int main() { vector<int> value = {21,43,12,22,12,53,21,34,1}; vector<int> weight = {14,23,54,33,11,3,7,24,2}; int capacity = 50; // 测量knapSackUnlimited2函数的运行时间 auto start1 = std::chrono::high_resolution_clock::now(); knapSackUnlimited(weight, value, capacity);//从左到右模型 auto end1 = std::chrono::high_resolution_clock::now(); auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1); // 测量knapSackUnlimited函数的运行时间 auto start2 = std::chrono::high_resolution_clock::now(); knapSackUnlimited1(weight, value, capacity);//每一种都尝试模型 auto end2 = std::chrono::high_resolution_clock::now(); auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2); // 输出运行时间 std::cout << "knapSackUnlimited运行时间: " << duration1.count() << " 微秒" << std::endl; std::cout << "knapSackUnlimited1运行时间: " << duration2.count() << " 微秒" << std::endl; }运行结果如下：
knapSackUnlimited运行时间: 1071 微秒 knapSackUnlimited1运行时间: 5275539 微秒差距还是非常明显的。但这只是对暴力递归而言，改成动态规划后二者都是双层 for 循环，时间复杂度并没有差别。个人认为“每一种都尝试”更好理解，但“从左到右”模型更优雅美观。