博客

给定一个背包，容量capacity。现有一堆物品，每个物品 i 的重量为 w[i] ，价值为 v[i] ，给定的数据内容如下所示。

int[] w = {2, 3, 4, 5};   //物品重量
int[] v = {3, 4, 5, 6};   //物品价值
int capacity = 8;         //背包容量

要解决的问题是，如何将物品放入背包，从而获得最大的价值。（0-1背包指定了，一个物品，要么放，要么不放，不能拆开）

所以考虑到每一个物品，它都有两种决策：放或者不放

可以放入背包的前提是 w[i]<=capacity

对于每个物品，如果可以放入背包，即满足 w[i]<=capacity 条件，背包的价值就会在以下两个情况间选择较大值：

1. 当前物品放入背包：因为已经确定了当前物品 i 是要放入，因此背包容量变为 nowCapacity = 原capacity-w[i] ，总价值 = 前 i-1 个物品放入nowCapacity 背包中的价值

2. 当前物品不放入背包：总价值 = 前 i-1 个物品放入capacity背包中的价值

归结成符号语言

total = max(value[i - 1][capacity], value[i - 1][capacity - w[i]] + v[i]);

如果不满足 w[i]<=capacity ，就无法放入背包，等同于上述情况2，此时归结为符号语言

total = value[i - 1][capacity]

因此，我们用一张表来记录整个放物品的过程，行表示第 i （这个 i 是从下标1开始的）件物品，列表示背包容量

用二维数组记录这张表，dp[nums+1][capacity+1]，dp[i][j] 表示背包容量为 j 时，放前 i （下标从1开始）件物品，此时获得的最大价值。

最终的结果就是 dp[nums+1][capacity+1] 的值。

整个核心代码如下：

if (j >= w[i - 1]) {
     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
} 
else {
     dp[i][j] = dp[i - 1][j];
}

因为物品的重量、价值数组下标从0开始，所以在取数的时候要减1

完整代码

public class 背包问题 {
    public static void main(String[] args) {
        int[] w = {2, 3, 4, 5};
        int[] v = {3, 4, 5, 6};
        int capacity = 8;
        int num = w.length;
        int[][] dp = new int[num + 1][capacity + 1];
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j >= w[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[num][capacity]);
    }
}

回溯寻找放入背包的物品

public void findWhat(int i, int j) {                
    if (i >= 1) {
        // 第i件商品没放
        if (dp[i][j] == dp[i - 1][j]) {
            item[i] = 0;
            findWhat(i - 1, j);
        }
        //第i件商品放了
        else if (j - w[i - 1] >= 0 && dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]) {
            item[i] = 1;
            findWhat(i - 1, j - w[i - 1]);
        }
    }
}

带有回溯物品放入情况的完整代码

public class 背包问题 {
    public static int[][] dp;
    public static int[] item;
    public static int[] w;
    public static int[] v;

    public static void main(String[] args) {
        w = new int[]{2, 3, 4, 5};
        v = new int[]{3, 4, 5, 6};
        int capacity = 8;
        int num = w.length;
        dp = new int[num + 1][capacity + 1];
        item = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j >= w[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[num][capacity]);
        findWhat(num, capacity);
        for (int i = 1; i <= num; i++) {
            System.out.print(item[i] + " ");
        }
        System.out.println();
    }

    public static void findWhat(int i, int j) {                
        if (i >= 1) {
            // 第i件商品没放
            if (dp[i][j] == dp[i - 1][j]) {
                item[i] = 0;
                findWhat(i - 1, j);
            }
            //第i件商品放了
            else if (j - w[i - 1] >= 0 && dp[i][j] == dp[i - 1][j - w[i - 1]] + v[i - 1]) {
                item[i] = 1;
                findWhat(i - 1, j - w[i - 1]);
            }
        }
    }
}
// 输出
// 10
// 0 1 0 1 

可以进行空间压缩