动态规划的主要思想:将问题分解为多个阶段,每个阶段对应一个决策。记录每一个阶段可达的状态集合(去掉重复的),然后通过当前阶段的状态集合来推导下一个阶段的状态集合,动态地往前推进。
动态规划最经典问题:0-1背包问题,但是经典的0-1背包问题给每个物品赋予两种属性(重量、价值),往往初次看此问题时难度较大。为了便于理解,先从经典的0-1背包问题提取一种属性进行分析(重量),题目如下:
简单0-1背包问题:已知n个物品,每种物品对应有一个重量 weight
,给定一个背包可以装入物品的最大重量为 maxWeight
,求满足最大重量限制的情况下,背包中物品总重量的最大值是多少?
首先通过一个例子来分析简单0-1背包问题。假设总共有5种物品,即 n=5
,每个物品的重量为 weights=[2,2,4,6,3]
,最大重量 maxWeight=9
。如下表所示,表中的行表示第几个物品,表中的列表示物品的重量,记为 curWeight
,由于背包的最大重量 maxWeight=9
,因此,该背包总共有0~9种重量的可能。
> 初始状态如下表所示:
【简单0-1背包问题初始状态】
> 当第0号物品决策完之后,即将0号物品不放入背包或将0号物品放入背包,如果不放入背包,即 curWeight=0
,如果放入背包,即 curWeight=2
,改变表中的对应状态:
【简单0-1背包问题第0号物品决策后的状态】
> 当第1号物品决策完之后,即将1号物品不放入背包或将1号物品放入背包,如果不放入背包,基于 n=0
时的状态集合,该背包中的重量有两种可能,即 curWeight=0
或 curWeight=2
,如果放入背包,基于 n=0
时的状态集合,该背包中的重量有两种可能,即 curWeight=2
或 curWight=4
,综上,1号物品决策完之后,背包中的重量总共有三种可能,即 curWeight=0
、 curWeight=2
或 curWight=4
。改变表中的对应状态:
【简单0-1背包问题第1号物品决策后的状态】
> 当第2号物品决策完之后,表中状态如下所示:
【简单0-1背包问题第2号物品决策后的状态】
> 当第3号物品决策完之后,表中状态如下所示:
【简单0-1背包问题第3号物品决策后的状态】
> 当第4号物品决策完之后,表中状态如下所示:
【简单0-1背包问题第4号物品决策后的状态】
根据题目中最大重量 maxWeight=9
和上表可知,当前背包下物品总重量的最大值为9。
通过上述分析,再看看将上述过程转化为 java
代码,如下所示:
/** * 背包中物品总重量的最大值 * @param weight 每个物品的重量数组 * @param n 物品的个数 * @param maxWight 背包可承受的最大重量 * @return 背包中物品总重量的最大值 */public int getMaxWeightInPackage(int[] weight, int n, int maxWight){ int res = 0; Boolean[][] state = new Boolean[n][maxWight+1]; // 先申请状态数组,即上面的表格的初始化状态
// 对第0行进行特殊处理,手动标记 state[0][0] = true; // 将第0号物品不放入背包 state[0][weight[0]] = true; // 将第0号物品放入背包
// 依次对剩下的物品进行决策 for (int i=1; i<n; i++){ // 将第i号物品不放入背包 for (int j=0; j<=maxWight; j++){ if ( state[i-1][j] != null && state[i-1][j] == true){ state[i][j] = state[i-1][j]; } }
// 将第i号物品放入背包 for (int j=0; j<= (maxWight-weight[i]); j++){ if(state[i-1][j] != null && state[i-1][j] == true) state[i][j+weight[i]] = true; } }
// 在最后一行从后向前遍历 for (int i=maxWight; i>=0; i--){ if(state[n-1][i] != null && state[n-1][i] == true){ res = i; break; } } return res;}
从上述实例可知,对于每个物品都有两种决策方案,要么放入背包,要么不放入背包。将整个过程分解成n个部分,对于每个部分都有两种决策方案,当每个物品决策完之后(放入背包或不放入背包)背包中的重量有多种情况,也就是说达到多种不同的情况。把每一层重复的状态合并,只记录不同的状态,然后基于上一层的状态集合,来推导下一层的状态集合。当所有部分决策完之后,即可得到最终的状态集合,从状态集合中可以得到该背包中最大的重量。
实际上,这就是动态规划解决问题的基本思路。将问题分解为多个阶段,每个阶段对应一个决策。我们记录每一个阶段可达的状态集合(去掉重复的部分),然后通过当前的状态集合来推到下一阶段的状态集合,动态地往前推进。
从上述代码可知,该问题的时间复杂度为 O(n*weight)
,其中 n
为物品的个数, maxWeight
为背包可承载的最大重量,该问题的空间复杂度为 O(n*weight)
,其中 n
为物品的个数, maxWeight
为背包可承载的最大重量。
优化:事实上,只需要申请 weight+1
的一维数组即可解决这个问题。 java
代码如下:
public int getMaxWeightInPackage2(int[] weight, int n, int maxWight) { int res = 0; Boolean[] state = new Boolean[maxWight+1]; // 先申请状态数组
// 对第0行进行特殊处理,手动标记 state[0] = true; // 将第0号物品不放入背包 state[weight[0]] = true; // 将第0号武平放入背包
// 依次对剩下的物品进行决策 for (int i = 1; i < n; i++) { for (int j=maxWight-weight[i]; j>=0; j--){ // 把第i个物品放入背包中 if (state[j] != null && state[j] == true) state[j+weight[i]] = true; } }
// 在最后一行从后向前遍历 for (int i=maxWight; i>=0; i--){ if(state[i] != null && state[i] == true){ res = i; break; } }
return res;}
简单0-1背包问题问题分析完成后,接下来将价值属性也添加进入,升级为高级0-1背包问题,请查阅《数据结构与算法-动态规划(二)》。