Backpack II

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.

Challenge

memory is acceptable, can you do it in memory?

Think

• The same idea as the Backpack I.
• But the value on memo array should be the value of items in bag

Solution

    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[][] memo = new int[A.length+1][m+1];

         for(int i = 0; i < A.length; i++) {
            for(int j = 0;j <= m; j++) {
                if(j - A[i] >= 0)
                    memo[i+1][j] = Math.max(memo[i][j], memo[i][j - A[i]] + V[i]); // add the value
                else
                    memo[i+1][j] = memo[i][j];
            }
        }

        return memo[A.length][m];
    }

Think (Space Optimized)

• 1-D array with length of m
• memo[i] should be the max value with i size items
• NOTE: the iterate on size should be reversed, from m to 0 since the value come from j - A[i] that can be updated if we look the previous index

Solution

    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        int[] memo = new int[m+1];

         for(int i = 0; i < A.length; i++) {
            for(int j = m; j >= 0; j--) { // lookup by reversed order
                if(j - A[i] >= 0)
                    memo[j] = Math.max(memo[j], memo[j - A[i]] + V[i]);
            }
        }

        int maxVal = 0;
        for(int i = m; i >= 0; i--)
            maxVal = Math.max(maxVal, memo[i]);

        return maxVal;
    }