Given_n_items with size Ai, an integer_m_denotes the size of a backpack. How full you can fill this backpack?

Notice

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.

public 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
     */

    //transit this problem to: for all possible size 0 - m, whether the size can be fufilled
    //last step: if the i - 1th item enters the backpack for size m
    //sub problem: we need to know 
        //1.if the first i - 1 already fufills size m
        //2.if the first i - 1 can fufill m - A[i - 2]

    //f[i][j] represents whether the first i item can fufill j size
    //f[i][j] = f[i - 1][j] || f[i - 1][j - A[i - 1]]
    //ans = max j when f[i][j] is true
    public int backPack(int m, int[] A) {
        // write your code here
        if (m == 0) {
            return 0;
        }

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

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

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

        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= A[i-1] && f[i-1][j - A[i-1]]) {
                    f[i][j] = true;
                }

            }
        }


        for (j = m; j >= 0; j--) {
            if (f[n][j]) {
                return j;
            }
        }

        return 0;

    }
}

rolling array with O(n), two rows in the array

public 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
     */

    //transit this problem to: for all possible size 0 - m, whether the size can be fufilled
    //last step: if the i - 1th item enters the backpack for size m
    //sub problem: we need to know 
        //1.if the first i - 1 already fufills size m
        //2.if the first i - 1 can fufill m - A[i - 2]

    //f[i][j] represents whether the first i item can fufill j size
    //f[i][j] = f[i - 1][j] || f[i - 1][j - A[i - 1]]
    //ans = max j when f[i][j] is true
    public int backPack(int m, int[] A) {
        // write your code here
        if (m == 0) {
            return 0;
        }

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

        int i, j;
        int now = 0;
        int old = 0;
        f[0][0] = true;
        f[1][0] = true;

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

        for (i = 1; i <= n; i++) {
            old = now;
            now = 1 - now;
            for (j = 1; j <= m; j++) {
                f[now][j] = f[old][j];
                if (j >= A[i-1] && f[old][j - A[i-1]]) {
                    f[now][j] = true;
                }

            }
        }


        for (j = m; j >= 0; j--) {
            if (f[now][j]) {
                return j;
            }
        }

        return 0;

    }
}

use 1 dimension array

public 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
     */

    //transit this problem to: for all possible size 0 - m, whether the size can be fufilled
    //last step: if the i - 1th item enters the backpack for size m
    //sub problem: we need to know 
        //1.if the first i - 1 already fufills size m
        //2.if the first i - 1 can fufill m - A[i - 2]

    //f[i][j] represents whether the first i item can fufill j size
    //f[i][j] = f[i - 1][j] || f[i - 1][j - A[i - 1]]
    //ans = max j when f[i][j] is true
    public int backPack(int m, int[] A) {
        // write your code here
        if (m == 0) {
            return 0;
        }

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

        int i, j;
        int now = 0;
        int old = 0;
        f[0] = true;

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

        for (i = 1; i <= n; i++) {
            for (j = m; j >= 0; j--) {

                if (j >= A[i-1] && f[j - A[i-1]]) {
                    f[j] = true;
                }

            }
        }


        for (j = m; j >= 0; j--) {
            if (f[j]) {
                return j;
            }
        }

        return 0;

    }
}