Givenn_kind of items with size Aiand value Vi(each item has an infinite number available) and a backpack with size_m. What's the maximum value can you put into the backpack?

Notice

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

Have you met this question in a real interview?

Yes

Example

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

//transform this to the problem for each size 1 to m whether we can form it using the item and what's maximum value
    //last step: in the maximum solution,
              //a. the first i - 1 item already fufill
              //b. the first i - 1 item fufill m - k * A[i - 1]
    //f[i][j] represents the maximum value when we use the first i item to fullfill size j
    //f[i][j] = Max 0<=k {f[i - 1][j], f[i - 1][j - k * A[i - 1]]|j - k * A[i - 1] >= 0 && //f[i - 1][j - k * A[i - 1]] != -1
    //init
    //f[i][0] = 0;
    //f[0][j] = -1;

    public int backPackIII(int[] A, int[] V, int m) {
        // Write your code here
        if (m == 0) {
            return 0;
        }

        int n = A.length;
        int[][] f = new int[n + 1][m + 1];

        //init
        int i, j;
        for (i = 0; i <= n; i++) {
            f[i][0] = 0;
        }

        for (j = 1; j <= m; j++) {
            f[0][j] = -1; 
        }

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; ++j) {
                int k = 0;
                while (j - k * A[i - 1] >= 0) {
                    if (f[i - 1][j - k * A[i - 1]] != - 1) {
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
                    }
                    k++;
                }
            }
        }

        int ans = 0;
        for (j = 0; j <= m; j++) {
            ans = Math.max(ans, f[n][j]);
        }
        return ans;
    }

optimize time complexity (remove k)

public class Solution {
    /**
     * @param A an integer array
     * @param V an integer array
     * @param m an integer
     * @return an array
     */

    //transform this to the problem for each size 1 to m whether we can form it using the item and what's maximum value
    //last step: in the maximum solution,
              //a. the first i - 1 item already fufill
              //b. the first i - 1 item fufill m - k * A[i - 1]
    //f[i][j] represents the maximum value when we use the first i item to fullfill size j
    //f[i][j] = Max 0<=k {f[i - 1][j - k * A[i - 1]]|j - k * A[i - 1] >= 0 && //f[i - 1][j - k * A[i - 1]] != -1
    //init
    //f[i][0] = 0;
    //f[0][j] = -1;


    //with the optimization
    //now the f[i][j] represents the first KIND of the item to fullfill j size
    //f[i][j] = Max{f[i - 1][j], f[i][j - A[i - 1]] + V[i - 1]}
    public int backPackIII(int[] A, int[] V, int m) {
        // Write your code here
        if (m == 0) {
            return 0;
        }

        int n = A.length;
        int[][] f = new int[n + 1][m + 1];

        //init
        int i, j;
        for (i = 0; i <= n; i++) {
            f[i][0] = 0;
        }

        for (j = 1; j <= m; j++) {
            f[0][j] = -1;
        }

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j - A[i - 1] >= 0 && f[i][j - A[i - 1]] != -1) {
                    f[i][j] = Math.max(f[i][j], f[i][j - A[i - 1]] + V[i - 1]);
                }
            }
        }

        int ans = 0;
        for (j = 0; j <= m; j++) {
            ans = Math.max(ans, f[n][j]);
        }
        return ans;
    }


}

optimize space

public class Solution {
    /**
     * @param A an integer array
     * @param V an integer array
     * @param m an integer
     * @return an array
     */

    //transform this to the problem for each size 1 to m whether we can form it using the item and what's maximum value
    //last step: in the maximum solution,
              //a. the first i - 1 item already fufill
              //b. the first i - 1 item fufill m - k * A[i - 1]
    //f[i][j] represents the maximum value when we use the first i item to fullfill size j
    //f[i][j] = Max 0<=k {f[i - 1][j - k * A[i - 1]]|j - k * A[i - 1] >= 0 && //f[i - 1][j - k * A[i - 1]] != -1
    //init
    //f[i][0] = 0;
    //f[0][j] = -1;


    //with the optimization
    //now the f[i][j] represents the first KIND of the item to fullfill j size
    //f[i][j] = Max{f[i - 1][j], f[i][j - A[i - 1]] + V[i - 1]}
    public int backPackIII(int[] A, int[] V, int m) {
        // Write your code here
        if (m == 0) {
            return 0;
        }

        int n = A.length;
        int[] f = new int[m + 1];

        //init
        int i, j;
        f[0] = 0;
        for (j = 1; j <= m; j++) {
            f[j] = -1;
        }

        for (i = 1; i <= n; i++) {
            for (j = 0; j <= m; j++) {
                if (j - A[i - 1] >= 0 && f[j - A[i - 1]] != -1) {
                    f[j] = Math.max(f[j], f[j - A[i - 1]] + V[i - 1]);
                }
            }
        }

        int ans = 0;
        for (j = 0; j <= m; j++) {
            ans = Math.max(ans, f[j]);
        }
        return ans;
    }


}