数据结构与算法-动态规划(二)

用户3470542

发布于 2019-06-26 08:15:01

42500

代码可运行

文章被收录于专栏：算法半岛算法半岛

运行总次数：0

代码可运行

高级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;}