前言

浅谈上篇博客

上篇博客是我的第一篇博客，在写完那篇博客后我发现我对ST表的理解比我写博客之前更加透彻了，简单思考后我发现是由于我以前都是简单的学习算法和数据结构，对于一个问题不会去深刻地思考，但是在写博客时，为了防止出错，同时为了更好的讲解，我会去尽可能地查找资料，追究更深层次的问题，在这个过程中，我对算法的理解得到了提高。因此，为了提升我对动态规划问题的理解，我将在接下来一段时间内开始写关于动态规划的博客，这次我将先讲解动态规划中的背包问题。

关于这次博客想要说的话

如上文所说，这篇博客是为了加深对动态规划的理解，侧面说明了我对动态规划这方面的学习不是很好，如果在接下来对背包问题的讲解中出现了错误（希望没有问题），请及时告诉我，我将会在第一时间去重新研究并及时改正。

正文

背包问题在动态规划中非常常见一类问题，所以，了解背包问题可以帮助更好的帮助理解动态规划。

背包问题分为0/1背包问题、多重背包问题、完全背包问题和分组背包问题共四种，下面我将他们分开一一讲解。

由于设备限制，只好和上次一样只有文字和代码说明。非常抱歉。。。

0/1背包问题

介绍

0/1背包是背包问题的基础，其它背包问题或多或少都是从0/1背包的基础上来的，因此，学会0/1背包是学会其它背包的前提。

题目假设

假设我们现在拥有一个容积上限为V的背包，同时在我们的面前有n个物品，它们的体积和价值分别为v[ i ]和w[ i ] (1 <= i <= n)，我们需要在不超过背包容积的情况下尽可能装入总价值更高的物品，请求出最高总价值是多少。

错解

在初次见到此类问题时，我们容易想到用贪心去求解，乍一看这样好像挺合理，但只要我们简单思考就容易发现：一个物品的体积是固定的，我们不能只把它的一小部分装入背包。因此贪心是错误的解法。

思考

通过思考我们可以很容易发现当我们放入一个物品时，此时放入物品的总价值和总体积只与已经放入的物品有关，与还未放入的物品无关，这就满足了动态规划的无后效性（无后效性是指某个状态一旦确定，就不受之后决策的影响），因此我们可以用以下方法求解。

二维

文字说明

在求解此类问题时，我们可以建立一个二维数组dp[ i ][ j ]（ i 是考虑物品个数，j 是背包容积），其值表示总价值，我们依次枚举每个物品 i ( 1 <= i <= n)，同时限定放入该物品时背包的总容积为 j (0 <= j <= V)，此时我们分为两种情况：一，背包此时限定容积的不足以放入第 i 个物品，此时我们选择不放入该物品，则dp[ i ][ j ] = dp[ i - 1][ j ];二,背包的剩余体积足够放入第 i 个物品，这个时候我们就要考虑放入这个物品后我们得到的总价值是否大于不放入时的价值，若大于则放入，反之则不放入（因为我们限定了背包的体积，所以我们要放入该物品就需要把其中一些物品拿出来，这会导致物品总价值减少，若该物品的价值无法弥补减少的价值，则会导致放入该物品得到的总价值小于不放入时的价值），所以dp[ i ][ j ] = max(dp[i - 1][ j ],dp[i - 1][ j - v[ i ]] + w[ i ])。当我们把所有物品都考虑后，最后得到的值即为最大的总价值即dp[ n ][ V ];

代码说明

1 for (int i = 1; i <= n; i++){   //枚举每个物品
2     for (int j = 0; j <= V; j++){   //背包限定容积
3         if (j < v[i])   //如果背包限定的容积不足以放入第i个物品
4             dp[i][j] = dp[i - 1][j];
5         else
6             dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
7     }
8 }
9 int ans = dp[n][V];

一维

优势

比赛时，程序的空间往往会受到限制，而二维的空间复杂度为O（nV），有时会因为空间超限导致无法ac，这时我们就需要将数组压缩为一维来减少空间复杂度至O(V)。

原理

在二维中我们可以发现，dp[ i ][ ]的值只与dp[ i - 1][ ]的值有关，也就是说，第 i 行的值只与第 i - 1 行有关，与其他行无关，这时我们就可以再次使用这些空间在储存新的值，及将dp[ n ][ V ]优化为dp[V]。

文字说明

由上可知当 j < v[ i ]时，dp[ j ] 的值保持不变，当 j >= v[ i ]时，dp[ j ] = max(dp[ j ],dp[ j - v[ i ] ] + w[ i ] )。注意，在一维中我们需要将背包容积从大到小枚举，因为大容积的值需要从小容积的值得到，如果我们从小到大枚举，则我们会先更新小容积的值（错误更新dp[ i - 1 ]的值），当我们更新大容积的值时会把新更新的小容积的值计算在内导致出错，而从大到小枚举则可以保证每次更新时用到的值都是未考虑当前物品时的值。

最后得到的答案即为dp[ V ]。

代码说明

1 for (int i = 1; i <= n; i++){   //枚举每个物品
2     for (int j = V; j >= v[i]; j--){   //背包限定容积，注意从大到小
3         dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
4     }
5 }
6 int ans = dp[V];

多重背包问题

介绍

多重背包既然叫多重背包就说明它是背包问题，它与0/1背包的区别在于0/1背包中每种物品只有0和1两种状态，即选或不选，而多重背包则是每种物品可以有多个（大于或大于1）。假设第 i 种物品的体积为 v[ i ]，价值为 w[ i ],数量为 m[ i ],既然是每种物品是有限个，那么我们就可以把第 i 种物品的前 k 个( 0 <= k <= m[ i ] )归类为一种，每次枚举第 i 种物品时再依次枚举该种物品装入不同个数时的情况，即用三重循环进行状态转移，时间复杂度较高，因此我们可以用其它方法进行优化。下面我将介绍几种多重背包的求解方法。

普通方法

文字说明

每种物品可以选择不放置或者放置k( 0 <= k <= m[ i ])个，我们只需要在枚举第 i 个物品时把放置个数不同的情况中的最大价值算出来，方法与0/1背包类似。第一重循环枚举物品种类 i ，第二重循环枚举背包的容积，第三重循环枚举放入第 i 种物品的数目。即dp[ i ][ j ] = max{ max{ dp[ i ][ j - k * v[ i ] ] + k * w[ i ] } , dp[ i - 1 ][ j ] }（放入不同个数中的最高价值），我们也可以把它按照之前的方法压缩为一维数组，即 dp[ j ] = max{max{ dp[ j - k * v[ i ] ] + k * w[ i ] } , dp[ j ] }。

代码说明

1 //二维
2 for (int i = 1; i <= n; i++){   //枚举每个物品
3     for (int j = 0; j <= V; j++){
4         for(int k = 1; k <= m[i] && k * v[i] <= j; k++){//注意k的个数不能大于m[i]同时放入物品的总体积不能大于限定的容积
5             dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - k * v[i]] + k * w[i]);
6         }
7     }
8 }
9 int ans = dp[n][V];

1 //一维
2 for (int i = 1; i <= n; i++){   //枚举每个物品
3     for (int j = V; j >= v[i]; j--){   //背包限定容积，注意从大到小
4         for(int k = 1; k <= m[i] && k * v[i] <= j; k++){//注意k的个数不能大于m[i]同时放入物品的总体积不能大于限定的容积
5             dp[j] = max(dp[j],dp[j - k * v[i]] + k * w[i]);
6         }
7     }
8 }
9 int ans = dp[V];

二进制优化方法

文字说明

二进制优化方法是把每种物品的个数按照二进制进行拆分，使之成为一个新的物品，最后再按照新组成的物品进行0/1背包的求解。二进制拆分时要按照从小到大进行拆分，即 17 可以拆分为 1 + 2 + 4 + 8 + 2（2为余数）,即1到17中的任何数都可以有这些数组成，如 3 = 1 + 2， 5 = 1 + 4，7 = 1 + 2 +4。先对每种物品进行枚举并进行二进制，将每种拆分再进行枚举整合为一个新的物品，该物品的价值即为打包中物品的总价值，体积为打包中物品的总体积，之后利用二重循环进行0/1背包的求解。（感觉用代码比较好解释）

代码说明

 1 int cot = 0;//记录组成的新物品是第几个物品
 2 //组成新物品
 3 for (int i = 1; i <= n; i++){
 4     for (int j = 1; j <= m[i]; j <<= 1){//用位运算进行二进制拆分
 5         new_w[++cot] = j * w[i];
 6         new_v[cot] = j * v[i];
 7         m[i] -= j;
 8     }
 9     if (c[i]){//将剩余的物品组成一个新物品
10         new_w[++cot] = m[i] * w[i];
11         new_v[cot] = m[i] * v[i];
12     }
13 }

 1 //一维
 2 for (int i = 1; i <= cot; i++){
 3     for (int j = 0; j <= V; j++){
 4         if(j < new_v[i])
 5             dp[i][j] = dp[i - 1][j];
 6         else
 7             dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - new_v[i]] + new_w[i]);
 8     }
 9 }
10 int ans = dp[cot][V];

1 //一维
2 for (int i = 1; i <= cot; i++){   //枚举每个物品
3     for (int j = V; j >= new_v[i]; j--){   //背包限定容积，注意从大到小
4         dp[j] = max(dp[j],d[j - new_v[i]] + new_w[i]);
5     }
6 }
7 int ans = dp[V];

单调队列优化

还不熟悉，等我熟悉之后再过来写。。。

完全背包问题

介绍

完全背包问题是背包问题的一种，与0/1背包问题和多重背包问题不同，完全背包问题中每个物品的数量是无限的，可以选择任意多个。因此，完全背包问题也被称为无限背包问题。完全背包问题可以使用二进制优化算法进行优化，但是相比于多重背包问题，完全背包问题的时间复杂度已经比较低，因此二进制优化算法的优化效果并不明显。

假设

假设我们现在拥有一个容积上限为V的背包，同时在我们的面前有n种物品，每种物品可以无限制地放入背包，它们的体积和价值分别为v[ i ]和w[ i ] (1 <= i <= n)，我们需要在不超过背包容积的情况下尽可能装入总价值更高的物品，请求出最高总价值是多少。

思考

完全背包可以有无限个物品，因此我们可以在放入第 i 个物品上再次放入第 i 个物品，即我们可以用类似0/1背包的方法对完全背包进行求解，但是注意我们不仅需要考虑 i - 1种的情况，还要考虑 i 种的情况，此时我们可以用一维优化来更好的表达该状态转移即 dp[ j ] = max(dp[ j ], dp[j - v[ i ] + w[ i ]);因为0/1背包只能选择放入一个或者不放入，所以需要从大容积开始枚举，而完全背包可以多次放入，即前面已经放入第 i 个物品后仍然需要考虑第 i 个物品，则完全背包需要从小容积开始枚举（注意此处与0/1背包的不同），以便可以多次放入同一个物品。

代码

1 for (int i = 1; i <= n; i++){
2     for (int j = v[i]; j <= V; j++)//注意这里和0/1背包的差别
3         dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
4 }
5 int ans = dp[V];

分组背包问题

介绍

分组背包问题是背包问题的一种变体，与01背包、完全背包和多重背包问题不同，它将物品分为若干组，每组中的物品具有各自的体积与价值。

假设

假设我们现在拥有一个容积上限为V的背包，同时在我们的面前有n组物品，每组物品中有m[ i ]种物品，每个物品的体积和价值分别为v[ i ][ j ]和w[ i ][ j ] （i 为物品位于第 i 组，j 表面该物品是第 i 组中的第 j 个）。

文字说明

分组背包与0/1背包的差别在于出现了一个新的名为组的分类，但是每组只能放置一个物品，这就像0/1背包中的每种物品只能放置一个，此时我们只需要多加一层枚举每组中的物品 k （1 <= k <= m[ i ]）的循环，就可以用类似0/1背包的方法求解，具体方法请看代码。

代码

 1 //二维
 2 for (int i = 1; i <= n; i++){
 3     for (int j = 0; j <= V; j++){
 4         for (int k = 1; k <= m[i]; k++){//枚举
 5             if(j < v[i][k])
 6                 dp[i][j] = dp[i - 1][j];
 7             else
 8                 dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i][k]] + w[i][k]);
 9         }
10     }
11 }
12 int ans = dp[n][V];

 1 //一维
 2 for (int i = 1; i <= n; i++){
 3     for (int j = V; j >= 0; j--){
 4         for (int k = 1; k <= m[i]; k++){//枚举
 5             if(j >= v[i][k])
 6                 dp[j] = max(dp[j],dp[j - v[i][k]] + w[i][k]);
 7         }
 8     }
 9 }
10 int ans = dp[V];