动态规划-完全背包问题

动态规划-完全背包问题

1. 完全背包问题的叙述如下：

有n种物品，每种物品的单件重量为w[i]，价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无穷件。

2. 动态规划思想

   同样令dp[i][v]表示前i件物品恰好放入容量为v的背包中能获得的最大价值。

   和01背包一样，完全背包问题的每种物品都有两种策略，但是也有不同点。对第i件物品来说：

   1. 不放第i件物品，那么dp[i][v] = dp[i-1][v]，这步跟01背包是一样的。
   2. 放第i件物品。这里的处理和01背包有所不同，因为01背包的每个物品只能选择一个，因此选择放第i件物品就意味着必须转移到dp[i-1][v-w[i]]这个状态；但是完全背包问题不同，完全背包如果选择放第i件物品之后并不是转移到dp[i-1][v-w[i]]这个状态；而是转移到dp[i][v-w[i]]，这是因为每种物品可以放任意件（注意有容量的限制，因此还是有限的），放了第i件物品后还可以继续放第i件物品，直到第二维的v-w[i]无法保持大于等于0为止。

3. 状态转移方程

   由上面的分析可以写出状态转移方程：

   边界：dp[0][v] = 0 (0 <= v <= V)

   写成一维形式之后和01背包完全相同，唯一的区别在于这里v的枚举顺序是正向枚举，而01背包的一维形式中v必须是逆向枚举。完全背包的一维形式代码如下所示：

   for(int i = 1 ; i <= n ; i++){
       for(int v = w[i]; v <= V ; v++){// 正向枚举v
           dp[v] = max(dp[v],dp[v-w[i]] + c[i]);
       }
   }
   

4. 怎么理解必须正向枚举呢？

   

   如图11-11所示，求解dp[i][v]需要它左边的dp[i][v-w[i]]和它上方的dp[i-1][v]，显然如果让v从小到大枚举，dp[i][v-w[i]]就总是已经计算出的结果；而计算出dp[i][v]之后dp[i-1][v]就再也用不到了，可以直接覆盖。

5. 总结

   前面介绍了动态规划的相关概念，并求解了一些经典的动态规划模型。但是在实际碰到新的问题时，初学者总是容易陷入头脑一片空白，完全无法设计状态的情况，这是正常的现象，因为动态规划本身就需要经验的积累和大量的做题才能有较大的提高。不过从上面的经典模型中还是能总结出一些规律性的东西，先把前面介绍过的动态规划模型列举如下：

   1. 最大连续子序列和

      令dp[i]表示以A[i]作为末尾的连续序列的最大和

   2. 最长不下降子序列（LIS）

      令dp[i]表示以A[i]结尾的最长不下降子序列长度

   3. 最长公共子序列（LCS）

      令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度。

   4. 最长回文子串

      令dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串

   5. 数塔DP

      令dp[i][j]表示从第i行到第j个数字出发的到达最底层的所有路径上所能得到的最大和。

   6. DAG最长路

      令dp[i]表示从i号顶点出发能获得的最长路径长度

   7. 01背包

      令dp[i][v]表示前i件物品恰好装入容量为v的背包中能获得的最大价值。

   8. 完全背包

      令dp[i][v]表示前i件物品恰好放入容量为v的背包中能获得的最大价值。

6. 启发