01背包、多重背包、完全背包

发表评论

一、01背包

【问题】有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？并且假设背包容量为8。

i

1

2

3

4

w(体积)

2

3

4

5

v(价值)

3

4

5

6

解题思路

我们首先创建一个数组，这是我们后面需要用到的dp数组，数组行数为物品个数+1，列数为背包容量+1，并对首行和首列初始化为0（表示的是放入第0个物品即不放物品，和背包容量为0时的当前容量均为0）,便于后面的计算。

i/j 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0
2 0
3 0
4 0

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。

寻找递推关系式：

我们原先的问题就被拆解成一个个的小问题，即放入第i个物品或者不放入第i个物品。dp[i][j]表示的是当运算到第i个物品并且容量为j时，不论放不放第i个物品的最优解。

有两种可能性：

    1. 当前包的生于容量比该商品体积小，装不下，此时的价值与前一个即i-1个的价值是一样的，即dp[i][j] = dp[i-1][j]；
    2. 还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即
dp[i][j] = max( dp[i-1][j] , dp[i-1][j-w[i]]+v[i] )

其中dp[i-1][j]表示不装第i个物品。

dp[i-1][j-w[i]]+v[i]表示如果装了第i个物品，则用上一行的j-w[i]加上当前的价值v[i]，即为背包空余出w[i]的空间来装第i个物品，最后加上其价值。

运算

逐行进行填表，最后右下角的值就是我们要的答案

i/j 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 3 3 3 3 3 3 3
2 0 0 3 4 4 7 7 7 7
3 0 0 3 4 5 7 8 9 9
4 0 0 3 4 5 7 8 9 10

编程实现

public void backpack(int[] weight, int[] value, int capacity)//动态规划
    {
        int[][] dp = new int[weight.length + 1][capacity + 1];
        int n = weight.length, i, j;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= capacity; j++) {
                //当前容量小于物品容量时，直接继承上一个的结果
                if (j < weight[i-1]){
                    dp[i][j] = dp[i - 1][j];
                }
                //可以装填,选取最大的进行装填
                else{
                    dp[i][j]=Math.max(dp[i-1][j], dp[i - 1][j - weight[i-1]] + value[i-1]);
                }
            }
        }

        System.out.println("背包的最优解为:"+dp[dp.length-1][dp[0].length-1]);
        //输出都放入了哪些物品
        i=dp.length-1;
        j=dp[0].length-1;
        while(i>0){
            if(dp[i-1][j]==dp[i][j]);
            else{
                System.out.println(i);
                j=j-weight[i-1];
            }
            i--;
        }
    }

空间优化的解

我们从上述程序可以看到，每行运算的时候，所需要的只是上一行的数据，并且用到的是比它j更往前的数据，所以我们可以将数组压缩成一维数组。

public void backpack(int[] weight, int[] value, int capacity){
    int[] dp = new int[capacity + 1];
    int n = weight.length, i, j;
    for (i = 0; i < n; i++) {
        for (j = capacity; j >= 0; j--) {
            if (j >= weight[i] && dp[j] <= dp[j - weight[i]] + value[i]) {
                dp[j] = dp[j - weight[i]] + value[i];
            }
        }
    }
    System.out.println("背包的最优解为:" + dp[dp.length - 1]);
}

完全背包

有N 种物品和一个容量为Capacity的背包，每种物品都有无限件可用。放入第i 种物品的费用是W[i]，价值是V[i]。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

思路

这个问题非常类似于01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0 件、取1 件、取2件……直至取[ j / W[i] ]件等许多种。如果仍然按照解01 背包时的思路，令dp[i,j] 表示前i种物品恰放入一个容量为j的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

dp[i][j] = max( dp[i-1][j] , dp[i][j-w[i]]+v[i] )

编程实现

public void backpack(int[] weight, int[] value, int capacity)//动态规划
{
    int[][] dp = new int[weight.length + 1][capacity + 1];
    int n = weight.length, i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= capacity; j++) {
            //当前容量小于物品容量时，直接继承上一个的结果
            if (j < weight[i-1]){
                dp[i][j] = dp[i - 1][j];
            }
            //可以装填,选取最大的进行装填
            else{
                dp[i][j]=Math.max(dp[i-1][j], dp[i][j - weight[i-1]] + value[i-1]);
            }
        }
    }

    System.out.println("背包的最优解为:"+dp[dp.length-1][dp[0].length-1]);
    //输出都放入了哪些物品
    i=dp.length-1;
    j=dp[0].length-1;
    while(i>0){
        if(dp[i-1][j]==dp[i][j])
            i--;
        else{
            System.out.println(i);
            j=j-weight[i-1];
            if(j<0)
                break;
        }

    }
}

空间优化的解

由于完全背包每一行运算的时候，会用到之前运算的解，所以相对于01背包，他们的区别是，j从0到高进行遍历。

public void backpack(int[] weight, int[] value, int capacity) {
        int[] dp = new int[capacity + 1];
        int n = weight.length, i, j;
        for (i = 0; i < n; i++) {
            for (j = 0; j <=capacity; j++) {
                if (j >= weight[i] && dp[j] <= dp[j - weight[i]] + value[i]) {
                    dp[j] = dp[j - weight[i]] + value[i];
                }
            }
        }
        System.out.println("背包的最优解为:" + dp[dp.length - 1]);
    }

多重背包

有 N 种物品和一个容量为 Capacity 的背包。第i 种物品最多有 M[i] 件可用，每件耗费的空间是W[i]，价值是V[i]。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

思路

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。因为对于第i 种物品有 M[i] + 1 种策略：取0 件，取1 件……取 M[i] 件。令 dp[i][j] 表示前i种物品恰放入一个容量为j 的背包的最大价值，则有状态转移方程：

dp[i][j] = max( dp[i-1][j] , dp[i][j - k*w[i]] + k*v[i] )

这里不采用dp[i][j-w[i]]+v[i]的原因是这种方式无法计算已经放入了多少个i物品。

编程实现

public void backpack(int[] weight, int[] value, int[] num, int capacity)//动态规划
{
    int[][] dp = new int[weight.length + 1][capacity + 1];
    int n = weight.length, i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= capacity; j++) {
            //当前容量小于物品容量时，直接继承上一个的结果
            if (j < weight[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            }
            //可以装填,选取最大的进行装填
            else {
                int count = Math.min(num[i-1], j / weight[i-1]);
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= count; k++)
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * weight[i - 1]] + k * value[i - 1]);
            }
        }
    }
}