0-1背包变形

代码和0-1背包非常之像，只是由原来的容量固定，求最大价值，最小邮票数是每个邮票的价值(权重)一样，都为1(枚)，在背包大小固定的情况，求最少的邮票数。

// runtime: 4ms
// space: 496K
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX = 100000;

int main() {
    int total, n;
    while (cin>> total >> n) {
        int stamp[n + 1];
        int dp[n + 1][total + 1]; // dp[i][j] stands for min number of
        for (int i = 1; i <= n; ++i) {
            cin >> stamp[i];

        } // end of input

        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= total; ++j) {
                dp[i][j] = MAX;
            }
        } // initialize dp
        dp[0][0] = 0; // very important

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= total; ++j) {
                if (j < stamp[i]) { // can not select this stamp
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                else { // select this stamp
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - stamp[i]] + 1); // +1 means plus one stamp.
                }
            }
        }

        if (dp[n][total] == MAX) // can not combined into TOTAL
            cout << 0 << endl;
        else
            cout <<dp[n][total] << endl;
    }
    return 0;
}