Backpack

• LintCode: No.92-Backpack
• Problem:

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

• 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.
  

• Note:

  You can not divide any item into small pieces.
  

• Analysis:
  i : the (1 ~ i)th items.
  j : the backpack size.
  A[n] : items
  dp[i][j]: the max size to fulfill the size j of backpack using 1 ~ ith items. Recursion:

   dp[i][j] =  dp[i - 1][j], if A[i] > j, last state
   or
   dp[i][j] =  Max{dp[i - 1][j] , dp[i - 1][j - A[i]] + A[i]}, otherwise, find max size
  

  Optimze:

   weight[j] = j > A[i] && weight[j - A[i]], j is backpack size, weight[j] backpack size j could be fulfilled or not.
  

• Java:

  *2D Array:
    public class Solution {
        public int backPack(int m, int[] A) {
            // write your code here
            if (A == null || A.length == 0 || m <= 0) { 
                return 0;
            }
            int n = A.length;
            int[][] array = new int[n + 1][m + 1];
            for (int i = 1; i < n + 1; i++) { // 0 ~ ith item
                for (int j = 1; j < m + 1; j++) {
                    if (A[i - 1] > j) {
                        array[i][j] = array[i - 1][j];
                    } else {
                        array[i][j] = Math.max(array[i - 1][j], array[i - 1][j - A[i - 1]] + A[i - 1]);
                    }
                }
            }
            return array[n][m];
        }
    }
  *1D Array:  
    public class Solution {
        public int backPack(int m, int[] A) {
        // write your code here
            if (A == null || A.length == 0 || m <= 0) { 
            return 0;
            }
            boolean[] weight = new boolean[m + 1];
            Arrays.fill(weight, false);
            weight[0] = true;
            for (int i = 0; i < A.length; i++) {
                for (int j = m; j > 0; j--) {
                    if (j >= A[i] && weight[j - A[i]]) {
                        weight[j] = true;
                    }
                }
             }
            int result = 0;
            for (int i = m; i > 0; i--) {
                if (weight[i] == true) {
                    result = i;
                    break;
                }
            }
            return result;
        }
    }
  

• Time Complexity:
  n is number of items, m is 1 ~ m backpack size
  2D Array:O(n x m)
  1D Array:O(n x m)

• Space Complexity:
  n is number of items, m is 1 ~ m backpack size
  2D Array:O(n x m)
  1D Array:O(m)