Stamps

stamps

Algorithm

Maintain an array that holds the minimum number of coins needed to make a certain value. Then run DP; for each coin, update the array with the minimum number of coins needed to make each value using the current coin.

C++

#include <bits/stdc++.h>
using namespace std;

void setio(string s) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

int main() {
    setio("stamps");

    int k, n;
    cin >> k >> n;
    vector<int> stamps(n);
    for (int i=0; i<n; i++) {
        cin >> stamps[i];
    }
    int max = k * (*max_element(stamps.begin(), stamps.end()));

    int dp[200 * 10002];
    for (int i=0; i<max+1; i++) {
        dp[i] = 201;
    }
    dp[0] = 0;
    for (int i=0; i<n; i++) {
        for (int val=0; val<max+1; val++) {
            if (dp[val] < k && dp[val + stamps[i]] > dp[val] + 1) {
                dp[val + stamps[i]] = dp[val] + 1;
            }
        }
    }
    int res = 0;
    for (int i=0; i<max+1; i++) {
        if (dp[i] > k) break;
        res = i;
    }
    cout << res << endl;
}