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 have4
items 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.
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\];
}
};