清华大学机试 需要重点二刷 *第一次见到最小值背包问题

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn = 110;
const int cap = 21;
const int INF = 10000000;
int m, n;
int dp[maxn];
int w[cap];

int main() {
    while (cin >> m) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
        }
        fill(dp, dp + maxn, INF);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= w[i]; j--) {
                dp[j] = min(dp[j], dp[j - w[i]] + 1);
            }
        }
        if (dp[m] == INF)
            cout << 0 << endl;
        else {
            cout << dp[m] << endl;
        }
    }
}