经典背包问题的应用
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[]) {
int money[] = {1, 5, 10, 20, 50, 100};
int sum = 100;
if (argc > 1) {
sum = atoi(argv[1]);
}
vector<int> v(sum + 1, 0);
v[0] = 1;
for (int i=0; i<sizeof(money)/sizeof(int); ++i) {
for (int j=money[i]; j<=sum; ++j) {
v[j] = v[j] + v[j-money[i]];
}
}
cout << v[sum] << endl;
}