题解 | 【模板】完全背包

#牛客春招刷题训练营# + 链接

这题和01背包的区别主要再可以重复拿去,思路见注释↓

#include <climits>
#include <iostream>
#include <vector>
#define ll long long
#define pre(i, j, k) for(ll i = j; i < k; i++)
using namespace std;

我的快读第二个重载可以看看

/*rd*/template<typename T> inline void rd(T& bbv_value){char bbv_c = getchar();bbv_value = 0; while(bbv_c < '0' || bbv_c > '9'){bbv_c = getchar();}while(bbv_c <= '9' && bbv_c >= '0'){bbv_value = (bbv_value << 3)+(bbv_value << 1)+(bbv_c&15);bbv_c = getchar();}}/*第二个重载在这里*/template<typename T1, typename T2, typename ...Args> inline void rd(T1& bbv_1, T2& bbv_2, Args&... arg){rd(bbv_1); rd(bbv_2, arg...);}

int main() {
  int n, v;
  rd(n, v);
  vector<int> matter(n + 1), worthiness(n + 1);
  pre(i, 1, n+1) rd(matter[i], worthiness[i]);
  vector<int> dp(v + 1, 0), pro_two(v + 1, INT_MIN);
  pro_two[0] = 0;
  pre(i, 1, n + 1){
    pre(j, matter[i], v+1){//---------把循环正序,使得dp[i]在之前已经判断过是否要拿物体i的状态(dp[j - matter[i]])的基础上再次判断拿不拿物体i
      dp[j] = max(dp[j], dp[j - matter[i]] + worthiness[i]);
      pro_two[j] = max(pro_two[j], pro_two[j - matter[i]] + worthiness[i]);
    }
  }
  int pro_one_ans = 0;
  pre(i, 0, v + 1){
    pro_one_ans = max(pro_one_ans, dp[i]);
  }
  cout << pro_one_ans << endl;
  if (pro_two[v] < 0) cout << 0;
  else cout << pro_two[v];
}
// 64 位输出请用 printf("%lld")