BackPackII

• LintCode: No.125-BackpackII
• Problem:

  Given n items with size Ai and value Vi, and a backpack with size m.   
  What's the maximum value can you put into the backpack?
  

• Example:

   Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and   
   a backpack with size 10. The maximum value is 9.
  

• Note:

  You cannot divide item into small pieces and the total size of items   
  you choose should smaller or equal to m.
  

• Analysis:
  i : the (1 ~ i)th items.
  j : the backpack size.
  A[n] : items
  V[n] : value of items
  dp[i][j]: the max value with max size fulfilling 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]] + V[i]}, otherwise, find max size
  

  Optimze:

   weight[j] = Math.max(weight[j], V[i] + weight[j -A[i]]), j is backpack size, weight[j] current max value of backpack size j.
  

• Java:

  *2D Array:
    public class Solution {
        public int backPack(int m, int[] A, int[] V) {
            // 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]] + V[i - 1]);
                    }
                }
            }
            return array[n][m];
        }
    }
  *1D Array:  
    public class Solution {
        public int backPackII(int m, int[] A, int V[]) {
            // write your code here
            if (A == null || A.length == 0 || m <= 0) { 
                return 0;
            }
            int[] weight = new int[m + 1];
            for (int i = 0; i < A.length; i++) {
                for (int j = m; j > 0; j--) {
                    if (j >= A[i]) {
                        weight[j] = Math.max(weight[j], V[i] + weight[j - A[i]]);
                    } 
                }
            }
            return weight[m];
        }
    }
  

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