125. Backpack II 元素不重复使用

int backPackII(int m, vector<int> &A, vector<int> &V) { // write your code here // dp[i][j]: max value with i packsize and first j elements; // transition: 能放：1）放 2）不放 -> max(dp[i][j - 1], dp[i - A[j - 1]][j - 1] + V[j - 1]) // 不能放：dp[i][j] = dp[i][j - 1] // initial : dp[0][0] = 0; const int size = A.size(); vector<vector<int>> dp(m + 1, vector<int>(size + 1, 0)); for(int i = 1; i <= m; i++){ for(int j = 1; j <= size; j++){ if(i >= A[j - 1]){ dp[i][j] = max(dp[i][j - 1], dp[i - A[j - 1]][j - 1] + V[j - 1]); } else{ dp[i][j] = dp[i][j - 1]; } } } return dp[m][size]; }

优化成一维数组
/为什么从右往左？把原来的二维看成矩阵，每次更新都是基于上一行的结果，
所以在一维下，要从右往左，这样用于更新的值相当于是上一次的结果。如果从左往右，左边的值都变了。
int backPackII(int m, vector<int> &A, vector<int> &V) { // write your code here // dp[i][j]: max value with i packsize and first j elements; // transition: 能放：1）放 2）不放 -> max(dp[i][j - 1], dp[i - A[j - 1]][j - 1] + V[j - 1]) // 不能放：dp[i][j] = dp[i][j - 1] // initial : dp[0][0] = 0; const int size = A.size(); //vector<vector<int>> dp(m + 1, vector<int>(size + 1, 0)); vector<int> dp(m + 1, 0); for(int i = 1; i <= size; i++){ for(int j = m; j >= A[i - 1]; j--){ //为什么从右往左？把原来的二维看成 //if(i >= A[j - 1]){ // dp[i][j] = max(dp[i][j - 1], dp[i - A[j - 1]][j - 1] + V[j - 1]); dp[j] = max(dp[j], dp[j - A[i - 1]] + V[i - 1]); //} // else{ // dp[i][j] = dp[i][j - 1]; // } } } //return dp[m][size]; return dp[m]; }