Backpack

Backpack (0 - 1 背包问题)

0-1 knapsack problem

单次选择 + 最大体积

Question

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Notice

You can not divide any item into small pieces.

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

Tags

LintCode Copyright Dynamic Programming Backpack

Related Problems

Medium Backpack VI 30 % Medium Backpack V 38 % Medium Backpack IV 36 % Hard Backpack III 50 % Medium Backpack II 37 %

Analysis

背包问题序列I

要点： 单次选择+最大体积

常用是DP，但也可以用递归+记忆化搜索来做。

这个问题没有给每个物品的价值，也没有问最多能获得多少价值，而是问最多能装多满。

实际上在这里，如果我们把每个物品的大小当作每个物品的价值，就可以完美解决这个问题。

Solution

Preferred Solution

2D - DP

状态：

dp[i][j] - 代表在前 i 件物品中选择若干件，这若干件物品的体积和不超过 j 的情况下，所能获得的最大容量

外层循环A[i], 内层循环j

状态转移：

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

2D DP

    public int backPack(int m, int[] A) {
        int[][] dp = new int[A.length + 1][m + 1];
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + A[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[A.length][m];
    }

Or Another 2D DP

   public int backPackI(int m, int[] A) {
        int dp[][] = new int[A.length + 1][m + 1];
        for(int i = 1; i < A.length + 1; i++){
            for(int j = 0; j < m + 1; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= A[i - 1]){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j - A[i-1]] + A[i-1]);
                }
            }
        }
        return dp[A.length][m];
    }

1D - DP

State: 数组dp[i]表示书包空间为i的时候能装的A物品最大容量

动规经典题目，用数组dp[i]表示书包空间为i的时候能装的A物品最大容量。

两次循环，外部遍历数组A，内部反向遍历数组dp，若j即背包容量大于等于物品体积A[i]，则取前i - 1次循环求得的最大容量dp[j]，和背包体积为j - A[i]时的最大容量dp[j - A[i]]与第i个物品体积A[i]之和即dp[j - A[i]] + A[i]的较大值，作为本次循环后的最大容量dp[i]。

注意dp[]的空间要给m+1，因为我们要求的是第m+1个值dp[m]，否则会抛出OutOfBoundException。

一维数组优化：

在第 i 层循环初 dp[j] 存的相当于 dp[i - 1][j] 的值，因为在更新dp[j]时用到了 dp[j - A[i]], 由于内层循环倒序，所以dp[j - A[i]] 未被更新，因此代表了dp[i-1][j - A[i]]。

1D space optimized:

public class Solution {
    public int backPack(int m, int[] A) {
        int[] dp = new int[m+1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j > 0; j--) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
                }
            }
        }
        return dp[m];
    }
}

1D DP

j = m, m-1, ..., A[i]

    public int backPack(int m, int[] A) {
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = m; j >= A[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - A[i]] + A[i]);
            }
        }
        return dp[m];
    }

Another DP Approach (NOT Preferred)

2D with O(n * m) time and O(n * m) space.

动态规划4要素

• State:

  • f[i][S] “前i”个物品，取出一些能否组成和为S

• Function:

  • f[i][S] = f[i-1][S - a[i]] or f[i-1][S]

• Initialize:

  • f[i][0] = true; f[0][1..target] = false

• Answer:

  • 检查所有的f[n][j]

O(n * S) ， 滚动数组优化

注意这里A[i - 1]的数组下标，因为新建的是i = 1, ..., A.length

public class Solution {
    /**
    * @param m: An integer m denotes the size of a backpack
    * @param A: Given n items with size A[i]
    * @return: The maximum size
    */
    public int backPack(int m, int[] A) {
        boolean[][] dp = new boolean[A.length + 1][m + 1];

        dp[0][0] = true;

        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j] || (j - A[i - 1] >= 0 && dp[i - 1][j - A[i - 1]]);
            }
        }

        for (int j = m; j >= 0; j--) {
            if (dp[A.length][j]) {
                return j;
            }
        }

        return 0;
    }
}

1D version with O(n * m) time and O(m) memory.

public class Solution {
    /**
    * @param m: An integer m denotes the size of a backpack
    * @param A: Given n items with size A[i]
    * @return: The maximum size
    */
    public int backPack(int m, int[] A) {
        if (A.length == 0) return 0;

        int n = A.length;
        boolean[] dp = new boolean[m + 1];
        Arrays.fill(dp, false);
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 0; j--) {
                if (j - A[i - 1] >= 0 && dp[j - A[i - 1]]) {
                    dp[j] = dp[j - A[i - 1]];
                }
            }
        }


        for (int i = m; i >= 0;i--) {
            if (dp[i]) return i;
        }


        return 0;
    }
}

Memoization + Search

https://www.jiuzhang.com/solution/backpack/#tag-other

    int max =  Integer.MAX_VALUE;
    public int backPack(int m, int[] A) {

        Arrays.sort(A);
        boolean[] visited = new boolean[m + 1];
        int[] memo = new int[m + 1];
        dfs( m , A , 0 ,visited , memo );
        return m - max ;

    }
    private int dfs( int target , int[] A , int startIndex , boolean[] visited , int[] memo){
        if(visited[target]){
            return memo[target];
        }
        int res = target;
        for(int i = startIndex ; i < A.length ; i++){
            if(target - A[i] >=  0){
                res = dfs( target - A[i] , A , i + 1 ,visited ,memo);
            }
            else{
                break;
            }
        }
        visited[target] = true;
        memo[target] = res;
        max = Math.min(max ,res);
        return res; 
    }

Reference

• Backpack - neverlandly - 博客园