题解 P1049 【装箱问题】

lrj124 · 2016-09-10 11:17:08 · 题解

#include <algorithm>
#include <iostream>
using namespace std;
int Min = 9999999,v[31],m,n;
inline void dfs(int now,int num) {
  Min = min(Min,now);  //取小值
  if (num == n+1) return;  //选完了
  if (now-v[num] >= 0) dfs(now-v[num],num+1);  //还可以装
  dfs(now,num+1);  //跳过
}
int main (){
  ios :: sync_with_stdio(false);
  cin >> m >> n;
  for (int i = 1;i <= n;i++) cin >> v[i];
  dfs(m,1);  //搜索
  cout << Min;
  return 0;
}