AcWing 1380. 邮票——背包问题
原题链接
简单
作者:
虹之间
,
2021-01-19 15:16:34
,
所有人可见
,
阅读 610
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e6 + 10;
int f[N]; // 拼接出价值为N最少需要多少张邮票
int main()
{
ios::sync_with_stdio(false);
int k, n; cin >> k >> n;
int m = k * 10000;
for(int i = 0; i <= m; i ++ ) f[i] = N;
f[0] = 0;
for(int i = 0; i < n; i ++ ) {
int v; cin >> v;
for(int j = v; j <= m; j ++ ){
int t = f[j - v] + 1;
if(t < f[j]) f[j] = t;
}
}
int res = 0;
while(f[++res] <= k);
cout << res - 1 << endl;
return 0;
}