http://www.lintcode.com/zh-cn/problem/backpack-ii/
class Solution {
public:
/**
* @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
*/
int backPackII(int m, vector<int> A, vector<int> V) {
// write your code here
int n = A.size();
vector<int> f(m + 1, 0);
for (int k = 0; k < n; k++) {
for (int i = m; i >= A[k]; i--) {
if (f[i-A[k]] + V[k] > f[i]) {
f[i] = f[i-A[k]] + V[k];
}
}
}
return f[m];
}
};
