classSolution { 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 */ intbackPackII(int m, vector<int> A, vector<int> V){ if (A.empty() || V.empty() || m < 1) { return0; } constint N = A.size() + 1; constint M = m + 1; vector<vector<int> > result; result.resize(N); for (vector<int>::size_type i = 0; i != N; ++i) { result[i].resize(M); std::fill(result[i].begin(), result[i].end(), 0); }
for (vector<int>::size_type i = 1; i != N; ++i) { for (int j = 0; j != M; ++j) { if (j < A[i - 1]) { result[i][j] = result[i - 1][j]; } else { int temp = result[i - 1][j - A[i - 1]] + V[i - 1]; result[i][j] = max(temp, result[i - 1][j]); } } }
publicclassSolution { /** * @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 */ publicintbackPackII(int m, int[] A, int V[]) { if (A == null || V == null || A.length == 0 || V.length == 0) return0; finalintN= A.length; finalintM= m; int[][] bp = newint[N + 1][M + 1]; for (inti=0; i < N; i++) { for (intj=0; j <= M; j++) { if (A[i] > j) { bp[i + 1][j] = bp[i][j]; } else { bp[i + 1][j] = Math.max(bp[i][j], bp[i][j - A[i]] + V[i]); } } } return bp[N][M]; } }
classSolution { 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 */ intbackPackII(int m, vector<int> A, vector<int> V){ if (A.empty() || V.empty() || m < 1) { return0; }
constint M = m + 1; vector<int> result; result.resize(M); std::fill(result.begin(), result.end(), 0);
for (vector<int>::size_type i = 0; i != A.size(); ++i) { for (int j = m; j >= 0; --j) { if (j < A[i]) { // result[j] = result[j]; } else { int temp = result[j - A[i]] + V[i]; result[j] = max(temp, result[j]); } } }