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

【模板】完全背包

https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=308&tqId=2032575&ru=/exam/oj&qru=/ta/algorithm-start/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D308

开始逐渐理解

#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;
}
全部评论

相关推荐

06-04 17:59
已编辑
长江大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务