题解 | 【模板】01背包

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  本体解题思路来自题解中C++的第一篇
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define pre(var, st, en) for (ll var = st; var < en; var++)
#define endl '\n'
#define kkk ' '
/*bb_makevec*/template<typename T> auto bb_makevec(T bbv_value){return bbv_value;}  template<typename T1, typename T2, typename... Args> auto bb_makevec(T1 n, T2 m, Args... arg){using newtype = decltype(bb_makevec(m, arg...)); return vector<newtype>(n, bb_makevec( m, arg...));}
/*print*/template<typename T> void print(T x, char bbv_end_char = 0){if (x < 10) putchar(x + '0'); else {print(x/10); putchar((x%10+'0'));} if (bbv_end_char != 0) putchar(bbv_end_char);}
int main() {
  int n, v;
  cin >> n >> v;
  vector<int> bulk(n, 0), value(n, 0);
  pre(i, 0, n){
    cin >> bulk[i] >> value[i];
  }
  auto a = bb_makevec(v + 1, 0);
  auto pre_er = bb_makevec(v + 1, INT_MIN);
  pre_er[0] = 0;
  for (int i = 0; i < n; i++){
    for (int j = v; j >= bulk[i]; j--){
      pre_er[j] = max(pre_er[j], pre_er[j - bulk[i]] + value[i]);//  对于问题二,把pre_er[0]初始化为0,其余初始化为-∞(此处取INT_MIN因为题目中的物品总价值不会超过这个数的绝对值)这样只有从0开始装满的价值才是正常的(正数)
      a[j] = max(a[j], a[j - bulk[i]] + value[i]);//  对于问题一，就是普通的01背包，状态a[j]表示考虑前i(循环变量)个物品,装入大小为j的空间产生的最大价值;因为每次经行状态转移用到的是上一个i的前部分数据所以j从后往前,以压缩空间
    }
  }
  int ans = 0;
  pre(i, 0, v + 1) ans = max(ans, a[i]);
  print(ans, endl);
  if (pre_er[v] < 0) print(0);//   如果是负数表示没法刚好装满
  else print(pre_er[v]);
  return 0;
}
// 64 位输出请用 printf("%lld")