01背包模型
做的时候没好好审题,一直按完全背包做的,无语子
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int f[30][N];
int main()
{
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i ++ )
f[0][i] = INF;
for (int i = 1; i <= n; i ++)
{
int v;
cin >> v;
for (int j = 1; j <= m; j ++)
{
f[i][j] = f[i - 1][j];
if (j >= v)
f[i][j] = min(f[i][j], f[i - 1][j - v] + 1);
}
}
cout << ((f[n][m] == INF) ? 0 : f[n][m]) << endl;
return 0;
}