题解 | [NOIP2001]装箱问题

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  本题其实我觉得C++题解中的第一个会更好，但是他的dp数组改为bool型会更好理解
#include <bitset>
#include <iostream>
#include <vector>
using namespace std;
int main() {
  bitset<20005> dp;//----------可简单理解成更省空间的布尔型数组
  int v, n;
  cin >> v >> n;
  vector<int> nn(n);
  for (int i = 0; i < n; i++){
    cin >> nn[i];
  }
  dp[0] = 1;
  for (int i = 0; i < n; i++){
    for (int j = v; j >= nn[i]; j--){//---------因为后面的数据更新依赖上一轮的前面的数据所以，从后往前递归
      dp[j] = dp[j] || dp[j - nn[i]];//---------若dp[j]为 <true> 则表示,只考虑前i个物体,可以组合出空间j
    }
  }
  for (int i = v; i >= 0; i--)
    if (dp[i]){
      cout << v - i;
      return 0;
    }
  return 0;
}
// 64 位输出请用 printf("%lld")