叙述动态规划内容中的状态概念（动态规划之0-1背包问题）

那一季剩男 2022-12-05 17:46:44

收藏赞分享

在前面文章的例子里面讲解了许多动态规划的问题，说明了哪些问题可以用动态规划来解决以降低时间复杂度。动态规划里有许多经典的问题，其中0-1背包问题是最基础的问题，下面将进行讲解什么是0-1背包问题及其讲解。

一、0-1背包问题

关于背包问题，可以参考如下：

根据维基百科，背包问题（Knapsack problem）是一种组合优化的NP完全（NP-Complete，NPC）问题。

问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。一般来讲，背包问题有以下几种分类：

1、01背包问题

2、完全背包问题

3、多重背包问题

其中最简单的背包问题为01背包问题，下面为维基百科里的一张图：

怎么把价值为4美元12kg，价值为2美元2kg，价值为1美元1kg，价值为10美元4kg，价值为2美元1kg的物品进入只有15kg的背包，使其价值最大。

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(1)

问题可以描述为：

1、问题描述

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(2)

01背包问题（01 knapsack problem）：一共有n件物品，第i件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限C的情况下，能够装入背包的最大价值是多少？

如果用暴力解法

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(3)

2、背包问题用贪心算法无法解决

例如，下图，如果有id为：0，1，2的3个物品，其重量weight[]为：1，2，3，其价值value[]为：6，10，12。通过公式v/w，得到其价值为：6，5，4，要放入到空间为5的背包里。如果先放价值高的，就是放id为0，重量为1，价值为6的；再放id为1，重量为2，价值为10的。这时占用的重量就为1 2=3，还剩下5-3=2的重量，所以此时已经不能再放id为0的物品。所以总的价值就是6 10=16。如下图所示

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(4)

然而，我们明显知道真正的最优方法为如下的方式，放id为1和id为2的物品，其重量为5，价值可以达到10 12=22。

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(5)

因此解决背包这种问题贪心算法是不适用的，还是要用到动态规划来解决。

二、状态定义与状态转移方程的确定

由上一篇文章我们得知要解决动态规划问题就是要定义好记忆化搜索数组和函数及函数的实现。我们先实现一下其代码过程，后面再分析代码实现具体的过程。

1、记忆化搜索数组的定义

memo[i,j]表示在前i件（包括i件）物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

2、状态定义与状态转移方程

状态定义（要求的结果）：F(n,C) 考虑将n个物品放进容量为C的背包，使得价值最大。本文的值就为memo[n - 1][C]

状态转移方程：F(i,c) 考虑将前i个物品放进容量为c的背包，得到的最大价值

i和c的含义：表示为考虑将前i个物品放进容量为c的背包

3、问题化解为求2个问题的最大值

这时要求解的问题可以化解为求下面2个问题的最大值

（1）第i个物品不放进背包里，这时的价值就是i-1时的价值：F(i-1,c)

（2）如果第i个可以放入来，且不超过容量C，这是的价值为第i个物品的价值加上前面i-1的价值，注意这时i-1的重量为c-w(i)：v(i) F(i-1, c-w(i) )

即问题变为求解（1）和（2）的最大值就可以。如下：

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(6)

千言万语还不如直接看代码来得实际。下面看2种方式的实现。

4、记忆化搜索实现

在看代码之前大家记得看上面记忆化搜索数组的定义，状态定义与状态转移方程。不要一头钻进代码里，要先理解函数定义。

private int[][] memo; 是一个二维数组，表示在前i件（包括i件）物品中选择若干件物品放在承重为 j 的背包中，可以取得的最大价值。

/// 背包问题 /// 记忆化搜索 /// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积 /// 空间复杂度: O(n * C) public class Solution1 { private int[][] memo; public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; memo = new int[n][C 1]; // 初始化数组 for(int i = 0; i < n; i ) for(int j = 0; j <= C; j ) memo[i][j] = -1; // 根据上面=》状态定义（要求的结果）：F(n,C)考虑将n个物品放进容量为C的背包，使得价值最大。 // 要求的问题就是最后一个n-1, 容量为C return bestValue(w, v, n - 1, C); } // 用 [0...index]的物品,填充容积为c的背包的最大价值 private int bestValue(int[] w, int[] v, int index, int c){ if(c <= 0 || index < 0) return 0; if(memo[index][c] != -1) return memo[index][c]; int res = bestValue(w, v, index-1, c); if(c >= w[index]) res = Math.max(res, v[index] bestValue(w, v, index - 1, c - w[index])); return memo[index][c] = res; } public static void main(String[] args) { } }

5、动态规划实现

动态规划的实现是自底向上实现，和记忆化的方向是相反的，但其记忆数组的定义是一样的。

/// 背包问题 /// 动态规划 /// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积 /// 空间复杂度: O(n * C) public class Solution2 { public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; int[][] memo = new int[n][C 1]; for(int j = 0 ; j <= C ; j ) memo[0][j] = (j >= w[0] ? v[0] : 0 ); for(int i = 1 ; i < n ; i ) for(int j = 0 ; j <= C ; j ){ memo[i][j] = memo[i-1][j]; if(j >= w[i]) memo[i][j] = Math.max(memo[i][j], v[i] memo[i - 1][j - w[i]]); } return memo[n - 1][C]; } public static void main(String[] args) { } }

三、示例分析

用上面的例子演示整个过程的示例分析：

3个物品，容量为5。其id为：0，1，2的3个物品，其重量weight[]为：1，2，3，其价值value[]为：6，10，12；放入到空间为5的背包里。

下面表格的蓝色行0，1，2，3，4，5表示容量数量的变化从0到5；蓝色列0，1，2为3个物品。表格表达的含义为：0，1，2的3个物品，其容量从0变化到5，各个情况的最大价值。

表格里的数值表示为价值，表示在前i件（包括i件）物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

1、刚开始都为空

叙述动态规划内容中的状态概念（动态规划之0-1背包问题）(7)