上一篇文章中的例子解释了动态规划的很多问题，并说明了哪些问题可以通过动态规划来解决，以降低时间复杂度。动态规划中有很多经典问题，但最基本的问题是0-1背包问题。我将解释什么是0-1背包问题及其解释。

一、0-1背包问题

有关背包问题，请参阅下文。

根据维基百科，背包问题是一个组合优化NP 完全（NPC）问题。

这个问题可以解释如下。给定一组物品，每个物品都有自己的重量和价格，我如何选择这些物品，使其在有限的总重量内具有最高的总价格？

虽然多项式时间复杂度的NPC问题无解，但可以使用动态规划来解决伪多项式时间复杂度的背包问题。一般来说，背包问题有以下几类：

1.01 背包问题

2.解决背包问题

3.多个背包问题

最简单的背包问题是01背包问题。这是来自维基百科的图表。

12公斤价值4美元，2公斤价值2美元，1公斤价值1美元，4公斤价值10美元，1公斤价值2美元，那么如何让重量仅为15公斤的背包发挥最大价值？

这个问题可以解释如下。

1、问题描述

01 背包问题：一共有n件物品，第i件物品的重量为w[i]，值为v[i]。如果总重量不超过背包限制C，背包中最多可以装载多少重量？

如果使用暴力解决方案

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

例如下图中，如果有三个ID 为0、1、2 的商品，则它们的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的权重，所以此时不能放置ID0的物品。因此，总值为6+10=16。如下所示

然而，很明显，实际最好的方法是：如果放置ID为1和ID 2的物品，它们的重量将为5，价值将达到10+12=22。

因此，不能应用贪心算法来解决背包问题，必须使用动态规划。

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

从上一篇文章中，我们了解到要解决动态规划问题，我们需要定义一个记忆的搜索数组和一个函数，以及该函数的实现。我们先来实现代码流程，然后再分析代码实现的具体过程。

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

memo[i,j] 表示选择前i 件（含）放入装有j 个物品的背包中得到的最大值。

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

状态定义（所需结果）：为了最大化F(n,C) 值，请考虑将n 件物品放入容量为C 的背包中。本文的值为memo[n – 1][C]

状态转移方程：F(i,c) 考虑将前i 件物品放入容量为c 的背包中所获得的最大值。

i和c的含义：当我们考虑将前i件物品放入容量为c的背包时表达。

3、问题化解为求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）的最大值。如下：

敲1000 个字并不像直接看代码那么实用。我们来看看这两个方法的实现。

4、记忆化搜索实现

在看代码之前一定要阅读上面记忆的搜索数组定义、状态定义和状态转移方程。与其深入代码，不如先了解函数定义。

private int[][] memo; 是从前i 件物品（包括i 件物品）中选择一些物品放入背包中得到的最大值，表示的一个二维数组。

///背包问题///内存搜索///时间复杂度： 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(‘w 或v 无效’); if(C 0) throw new IllegalArgumentException(‘C 必须大于或等于零。’); 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] 字段输入背包的容量To do 。 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、动态规划实现

编程是自动的。 自下而上的实现与memoization方向相反，但内存数组的定义是相同的。

///背包问题///动态规划///时间复杂度： 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 或v’); if(C 0) throw new IllegalArgumentException(‘C 必须大于或等于零。’); int n==0 || C==0) return int [] [] memo=;新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] ;=w[i]) memo[i][j]=Math.max(memo[i][j], v[i] + memo[i – 1][j – w[i] ]) } 返回备忘录[n – 1][C]; } public static void main(String[] args) { }}

三、示例分析

显示整个过程的示例分析。

3 件，容量5。将ID 为0、1、2、重量[] 1、2、3、价值[] 6、10、12 的三件物品放入空间5 的背包中。

下表中，蓝色行0、1、2、3、4、5代表容量数量从0到5的变化，蓝色列0、1、2代表三项。该表的含义是三项0、1、2，其容量从0到5变化，每种情况下都是最大值。

表中的数值表示选择前i件物品（包括i件物品）放入容量为j的背包时获得的最大值。

1. 最初一切都是空的。

2. 将ID 为0 的项目放入表中。 增加容量的值为：如果容量为0，则为0；如果容量为1，则为6。由于物品ID为0，重量为1，因此无论容量增加多少，其值都将是6。

3.如果放入ID为1的物品，重量为2，所以如果容量为1，则无法放入。最大值仍然是6，这是最后一项的值。

4、如果放入ID为1的物品，当其容量达到2时，可以放入ID为1的物品，但是v(i)+F(i-1, c-w(i) ) ), c-w根据(i )=》2-2=0，即ID为0的物品不能放入背包，其值为10。

5.我们回头看看，如果容量增加到3，我们就可以放置ID为0和ID 1的物品了。此时，项目值是它们的和10+6=16，这是匹配的。 v(i)+F( i-1, c-w(i) ), c-w(i) 比原来的6 大，所以此时变成了16。

即使增加到4个，原理也是一样的。

6. 当物品ID改为2，容量达到3时，还不能放入任何物品，因此之前状态下有两个物品，ID为0和ID 1，值为16。

7、当物品ID为2且容量达到4时，即可填充物品。根据v(i)+F(i-1,c-w(i))，将12+6与16进行比较，选择18。

8. 当到达最后一个时，容量将达到5，值为10+12=22。