数据结构与算法-动态规划(二)
高级0-1背包问题
高级0-1背包问题：已知n个物品，每种物品对应有重量 weight和价值 value两个属性，给定一个背包可以装入物品的最大重量为 maxWeight，求满足最大重量限制的情况下，背包中装入物品的总价值最大是多少？
实例分析：总共有5种物品，即 n=5，每个物品的重量为 weights=[2，2，4，6，3]，对应价值为 values=[3,4,8,9,6]，最大重量 maxWeight=9，求背包中可装如物品的总价值最大是多少？
如下表所示，表中行表示的第几个物品，表中的列表示物品的重量，由于背包的最大重量 maxWeight=9，因此，该背包总共有 0~9种重量的可能，表中的数据项表示价值，记为 curValue，初始状态下 curValue=-1。
> 初始状态如下表所示:
【升级0-1背包问题初始状态】
> 当第0号物品决策完之后，即不放入背包或放入背包，如果不放入背包，则在 curWeight=0的列 curValue=0，如果放入背包，即在 curWeight=2的列 curValue=3，改变表中的对应状态：
【升级0-1背包问题第0号物品决策后的状态 】
> 对于第1号物品，我们分将物品不放入背包和将物品放入背包这两种情况讨论:
> 对于第1号物品： 将物品( curWeight=2, curValue=4)不放入背包时：根据 n=0的状态集合可以得到 n=1的状态集合，如下所示：
【升级0-1背包问题第1号物品不放入背包】
> 对于第1号物品： 将物品( curWeight=2, curValue=4)放入背包时：根据 n=0的状态集合可以得到 n=1的状态集合，如下所示：
【升级0-1背包问题第1号物品放入背包】
> 对于 n=1时的第2列，选取当前状态的最大值为该列的状态值，即此时的4为 n=1时的第2列的状态值。
> 综上，对于1号物品决策完后，表中状态如下所示：
【升级0-1背包问题第1号物品决策后的状态】
> 当第2号物品决策完之后，表中状态如下所示：
【升级0-1背包问题第2号物品决策后的状态】
> 当第3号物品决策完之后，表中状态如下所示：
【升级01背包问题第3号物品决策后的状态】
> 当第4号物品决策完之后，表中状态如下所示：
【升级01背包问题第4号物品决策后的状态】
根据题意背包最大重量 maxWeight=9和上表可知，当前背包中装入物品的总价值最大为18。
将上述分析过程转化为 java代码：
/** * 求背包中装入物品的的最大总价值 * @param weights 每个物品的重量数组 * @param values 每个物品的价值数组 * @param n 物品的个数 * @param maxWeight 背包可承受的最大重量 * @return 背包中物品的最大总价值 */public int getMaxWeightInpackage(int[] weights, int[] values, int n, int maxWeight){ int res = -1; int[][] states = new int[n][maxWeight+1]; // 初始化states for (int i = 0; i < n; i++) { for (int j = 0; j <= maxWeight; j++) { states[i][j] = -1; } }
// 对第0行进行特殊处理，手动标记 states[0][0] = 0; // 将第0号物品不放入背包 states[0][weights[0]] = values[0]; // 将第0号物品放入背包
// 依次对剩下的物品进行决策 for (int i = 1; i < n; i++) { // 将第i号物品不放入背包 for (int j = 0; j <= maxWeight; j++) { if (states[i-1][j] != -1){ states[i][j] = states[i-1][j]; } }
// 将第i号物品放入背包 for (int j = 0; j <=(maxWeight-weights[i]) ; j++) { if (states[i-1][j] != -1){ states[i][j+weights[i]] = Math.max((states[i-1][j] + values[i]),(states[i][j+weights[i]])); } } }
// 求出背包中的总价值最大值 for (int i = 0; i <= maxWeight; i++) { res = Math.max(res, states[n-1][i]); } return res;} 从上述代码可知，该问题的时间复杂度为 O(n*weight)，其中 n为物品的个数， maxWeight为背包可承载的最大重量，该问题的空间复杂度为 O(n*weight)，其中 n为物品的个数， maxWeight为背包可承载的最大重量。
优化：事实上，只需要申请 weight+1的一维数组即可解决这个问题。 java代码如下：
/** * 求背包中装入物品的的最大总价值 * @param weights 每个物品的重量数组 * @param values 每个物品的价值数组 * @param n 物品的个数 * @param maxWeight 背包可承受的最大重量 * @return 背包中物品的最大总价值 */public int getMaxWeightInpackage2(int[] weights, int[] values, int n, int maxWeight){ int res = -1; int[] states = new int[maxWeight+1]; // 申请状态数组 for (int i = 0; i <=maxWeight ; i++) { // 初始化状态数组 states[i] = -1; }
// 对第0行进行特殊处理，手动标记 states[0] = 0; states[weights[0]] = values[0];
// 依次对剩下的物品进行决策 for (int i = 1; i < n; i++) { for (int j=maxWeight-weights[i]; j>=0; j--){ if(states[j] != -1){ states[j+weights[i]] = Math.max(states[j] + values[i], states[j+weights[i]]); // 更新states[j+weights[i]] } } }
// 在最后一行从后向前遍历 for (int i = 0; i <= maxWeight; i++) { res = Math.max(res, states[i]); } return res;}通过0-1背包问题初步了解了动态规划解决问题的过程后，我们接下来学习有关动态规划的理论知识，请查阅《数据结构与算法-动态规划(三)》。