0-1背包问题

问题

0-1背包是在 n 件物品取出若干件放在空间为 w 的背包里，每件物品的重量为 w1，w2至wn，与之相对应的价值为p1,p2至pn。0-1背包是背包问题中最简单的问题。0-1背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和重量两个属性。在0-1背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

解析

0-1背包问题是很明显的动态规划问题。

算法

设物品重量为 weights[] ，其相对应的价值 values[]。

共有 n 件物品。最大承重量为 w。

详细见解法1注释。

解法1

public void bag(int[] weights, int[] values, int n, int w){
     // dp[i][j] 代表前 i 件放入容量为 j的背包中的最大价值
    int[][] dp = new int[n + 1][w + 1];

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= w; j++){
            if(j >= weights[i]){ // 如果当前容量可以放入第 i 件物品
                // 根据最大价值原则，决定是否放入当前这件物品
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
            }else{
                // 放不下的话就不放
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][w];
}

解法2

解法1的空间占用较大，经过分析，对于解法1的 dp[i][j] 我们只需要知道左上角的值 dp[i - 1][j - weights[i]] 即可。所以使用一维数组即可。

public void bag(int[] weights, int[] values, int n, int w){
    int[] dp = new int[w + 1];

    for(int i = 1; i <= n; i++){
        for(int j = w; j >= w; j--){
            if(j >= weights[i]){ // 如果当前容量可以放入第 i 件物品
                // 根据最大价值原则，决定是否放入当前这件物品
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
    }
    return dp[w];
}