动态规划之0-1背包问题详解

前(fèi)言(huà)

最近几天准备软考，刚好就碰到一个0-1背包问题，题中给出的方法是使用动态规划（其实0-1背包问题如果穷举的话时间复杂度是指数级的，显然不合适），这个题一看一个二维表就知道是使用动态规划了（居然真有一个问是问采用什么设计策略，送2分），然后我就想到之前参加的蓝桥杯（暴力杯），在蓝桥杯中每年都有这样的题（遇能暴力求解的就暴力求了），于是最近就研究了一下这个0-1背包问题，不过感觉网上好像好多都说得不太明白，这里就来一个大白话0-1背包问题～

什么是背包问题

背包问题基本上都是一个包拿几样东西，这几样东西有两个参数，一个是重量（或者体积），一个是价值，背包能放下的东西有限（重量限制或者体积限制），问题就是能获得的最大价值是多少。（也有很多题直接不装了，我就告诉你背包问题，给我写代码）

为啥是0-1背包

学计算机的都知道计算机有一个类型是布尔(bool)，这个类型的参数只有0和1，也就是True和False的，说人话就是每样东西只有一个，你只能选择拿或者不拿，没有第二个相同的东西给你拿，所以0-1背包问题允许拿的东西都是有且只有一个，所以与它相对应的就是完全背包问题，也就是可以拿多个（通常不限），背包问题还有其他的类型，例如多背包问题，这里就不展开说咯。

举个栗子

这里我就以2019年下半年的软件设计师考试的题为例：

若五项物品的价值数组和重量数组分别为v[]={0,1,6,18,22,28}和w[]={0,1,2,5,6,7}，背包容量为T=11，则获得的最大价值为____。

（其实我不喜欢同一个东西列两个数组）上述的五个物品（价值0，质量0的物品直接可以忽略不计）可以列成下面的表格（我恳求小破站出一个可以放表格的功能）：

注意goods那行是我标注的序号

|   goods   |    1    |    2    |     3     |     4     |     5     |

|    value    |    1    |    6    |    18    |    22    |    28    |

|   weight   |    1    |    2    |     5     |     6     |     7     |

背包容量（最大承受重量）为11

然后一顿操作瞎猜，选择3号和4号恰好把背包放满，价值最大是40（答案的确是40）

那么使用动态规划怎么做的呢。

动态规划思路

那么既然靠猜显然不行，那么使用动态规划怎么做呢

动态规划的基本思想首先建立一个二维表格，这个表格的行数为物品的个数+1，例如上述的题目中一共有5个物品，那么这个表格一共有6行，如果你要问我为啥是6行不是5行，我觉得最说得通的就是会有一个都放不下的情况，另外计算机的第一个数都是从0开始，这样方便编程。另外，这个表格的列数为背包容量+1，为啥加1同理。这个表格里所有数值都表示“最大价值”。

（我把题复制一下，方便各位看题）

|   goods   |    1    |    2    |     3     |     4     |     5     |

|    value    |    1    |    6    |    18    |    22    |    28    |

|   weight   |    1    |    2    |     5     |     6     |     7     |

背包容量（最大承受重量）为11

所以上面的题就可以绘制成一个6x12的表格（行从0～5，列从0～11），先初始化都清零，这里为了方便各位看，我就不全设置为0了（不然容易眼花