92.Backpack (LintCode, 单次选择+最大体积)

Description

Given n _items with size _Ai, an integer _m _denotes the size of a backpack. How full you can fill this backpack?

You can not divide any item into small pieces.

Have you met this question in a real interview?

Yes

Example

If we have4items 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 is10. If the backpack size is12. 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.

Thoughts:

1. 0 - 1 backpack problem
2. Space-optimized Solution:
   1. dp[j] = for size j, there is a solution for current A[0, ... i] items
   2. dp[0] = True
   3. in reverse order: dp[j] |= dp[j - A[i]] # we can insert item A[i] into j
   4. solution : max i such that dp[i] == 1
3. Non-optimized Solution:
   1. dp[i][j]: for (i - 1) th item i, whether size j contain full bag (0th is for initial state)
   2. dp[.][0] = True
   3. in left-right order: dp[i][j] = dp[i - 1][j - A[i - 1]] for j >= A[i - 1]
4. real value Solution

Code T: 2614 ms O(m * n); S: O(m)

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
    """
    def backPack(self, m, A):
        # write your code here

        dp = [0 for _ in range(m + 1)]
        dp[0] = 1
        for i in range( len(A) ):
            for j in range(m, A[i ]-1, -1):
                dp[j] |= dp[j - A[i]]

        for i in range(m, -1, -1):
            if dp[i]:
                return i

        return 0

Code T: O(m * n) 6288 ms; S: O(m * n)

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
    """
    def backPack(self, m, A):
        # write your code here
        dp = [[0 for j in range(m + 1)] for i in range(len(A) + 1)]
        for i in range(len(dp)):
            dp[i][0] = 1
        # print('m + 1: {};  n + 1: {}'.format(len(dp),len(dp[0])))

        for i in range(1, len(A) + 1):
            for j in range (m + 1):
                # print('i: {}; j: {}'.format(i,j))
                dp[i][j] = dp[i-1][j]
                if j >= A[i-1] and dp[i - 1][j - A[i - 1]]:
                    dp[i][j] = 1

        for j in range(m, -1 , -1):
            if dp[len(A)][j]:
                return j

        return 0

Code T: O(m * n) 2397 ms; S: O(m)

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];
    }
}