题解 | #【模板】完全背包#

开始逐渐理解

#include <iostream>
#include <vector>
#include <climits>

int main(int argc, char *argv[]) {
  int count, size;
  
  std::cin >> count >> size;
  
  std::vector<std::vector<int>> objs(count, std::vector<int>(2, 0));
  
  for (int i = 0; i < count; ++i) {
    std::cin >> objs[i][0] >> objs[i][1];
  }
  
  //  dp[i] 表示容量为i的背包所能装的最大价值
  std::vector<int> dp(size + 1, 0);
  
  for (int i = 0; i < count; ++i) {
    for (int j = objs[i][0]; j <= size; ++j) {
      dp[j] = std::max(dp[j], dp[j - objs[i][0]] + objs[i][1]);
    }
  }
  
  std::cout << dp[size] << std::endl;
  
  for (int i = 1; i < dp.size(); ++i) {
    dp[i] = INT_MIN;
  }
  dp[0] = 0;
  
  
  for (int i = 0; i < count; ++i) {
    for (int j = objs[i][0]; j <= size; ++j) {
      dp[j] = std::max(dp[j], dp[j - objs[i][0]] + objs[i][1]);
    }
  }
  
  if (dp[size] < 0) {
    std::cout << 0 << std::endl;
  } else {
    std::cout << dp[size] << std::endl;
  }
  
  return 0;
}