Backpack II

Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?

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 size 10. The maximum value is 9.

Note

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

Challenge

O(n x m) memory is acceptable, can you do it in O(m) memory?

和上题一样，只是状态函数变为前i中取j个所能得到的最大值， 空间上改成滚动数组就行了。懒得改了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

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< vector<int> > tbl(n+1, vector<int>(m+1, INT_MIN)); for (int i=0; i<=n; i++){ tbl[i][0] = 0; } for (int i=1; i<=m; i++){ tbl[0][i]=0; } int res=INT_MIN; for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ tbl[i][j]=tbl[i-1][j]; if (j-A[i-1]>=0) tbl[i][j]=max(tbl[i][j],tbl[i-1][j-A[i-1]]+V[i-1]); } } return tbl[n][m]; } };