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

【模板】完全背包

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

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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