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.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

class Solution {

public:

/\*\*

 \* @param m: An integer m denotes the size of a backpack

 \* @param A: Given n items with size A\[i\]

 \* @return: The maximum size

 \*/

int backPack\(int m, vector<int> A\) {

    // write your code here

    const int n = A.size\(\);

    int dp\[2\]\[m + 1\];

    for \(int i = 0; i < 2;++i \){

        for \(int j = 0; j <= m; ++j \) {

            dp\[i\]\[j\] = 0;

        }

    }

    for \(int i = 1; i <= n; ++i\) {

        for \(int j = 1; j <= m; ++j\) {

            dp\[i%2\]\[j\] = dp\[\(i-1\)%2\]\[j\];

            if \(A\[i - 1\] <= j\) {

                dp\[i%2\]\[j\] = max\(dp\[i%2\]\[j\], dp\[\(i-1\)%2\]\[j - A\[i - 1\]\] + A\[i - 1\]\);

            }

        }

    }

    return dp\[n % 2\]\[m\];

}

};

results matching ""

    No results matching ""