题解 | #[NOIP2001]装箱问题#

背包看着就头疼

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char *argv[]) {
  int pack, objs;
  
  std::cin >> pack >> objs;
  
  std::vector<int> size(objs, 0);
  std::vector<int> dp(pack + 1, 0);
  
  for (int i = 0; i < objs; i++) {
    std::cin >> size[i];
  }
  
  for (int i = 0; i < objs; ++i) {
    for (int j = pack; j >= size[i]; --j) {
      dp[j] = std::max(dp[j], dp[j-size[i]]+size[i]);
    }
  }
  
  std::cout << pack - dp[pack] << std::endl;
  
  return 0;
}