文章
17
粉丝
166
获赞
6
访问
143.7k
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int INF = 1e9;
int a[N];
int f[N][N];
//f[i][j]前i张凑成j总值,最小的邮票数
int main()
{
int m, n;
while(cin >> m)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
//f[:][0] = 0
//f[0][:] = INF
//f[i][j] = min(f[i-1][j], f[i-1][j-a[i]] + 1)
//注意初始化为inf
memset(f, 0x3f, sizeof f);
for(int i = 0; i <= n; i++) f[i][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j >= a[i]) f[i][j] = min(f[i][j], f[i - 1][j - a[i]] + 1);
}
if(f[n][m] == 0x3f3f3f3f) cout << 0 << endl;
else cout << f[n][m] << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发