转载自：http://www.hankcs.com/program/cpp/poj-1742-coins.html
dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来）
如果dp[i - 1][j] >= 0(前i-1个数可以凑出j，那么第i个数根本用不着)直接为C[i]
dp[i][j] = 如果j < A[i]或者dp[i][j - a[i]] <=0 (面额太大或者在配更小的数的时候就用光了）-1
其他（将第i个数用掉一个） dp[i][j-a[i]] - 1
#include <iostream>
#include <algorithm>
using namespace std;
int dp[100 + 16][100000 + 16]; // dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个
int A[100 + 16];
int C[100 + 16];
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, m;
while(cin >> n >> m && n > 0)
{
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < n; ++i)
{
cin >> A[i];
}
for (int i = 0; i < n; ++i)
{
cin >> C[i];
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (dp[i][j] >= 0)
{
dp[i + 1][j] = C[i];
}
else if (j < A[i] // 用一个就超出，不能用
|| dp[i + 1][j - A[i]] <= 0) // 连凑比j小的数的时候都用完了，此时更加用完了
{
dp[i + 1][j] = -1;
}
else
{
dp[i + 1][j] = dp[i + 1][j - A[i]] - 1; // 用上了一个第i个硬币
}
}
}
int answer = count_if(dp[n] + 1, dp[n] + 1 + m , bind2nd(greater_equal<int>(), 0)); // 总额0不算在答案内
cout << answer << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}
///////////////////////////End Sub//////////////////////////////////
但是这样会MLE，所以需要减少一维
dp[j] := 在第i次循环时之前表示用前i-1种硬币凑成j时第i种硬币最多能剩余多少个（-1表示配不出来），循环之后就表示第i次的状态
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int dp[100000 + 16]; // dp[i][j] := 用前i种硬币凑成j时第i种硬币最多能剩余多少个
int A[100 + 16];
int C[100 + 16];
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n, m;
while(cin >> n >> m && n > 0)
{
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 0; i < n; ++i)
{
cin >> A[i];
}
for (int i = 0; i < n; ++i)
{
cin >> C[i];
}
for (int i = 0; i < n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (dp[j] >= 0)
{
dp[j] = C[i];
}
else if (j < A[i] // 用一个就超出，不能用
|| dp[j - A[i]] <= 0) // 连凑比j小的数的时候都用完了，此时更加用完了
{
dp[j] = -1;
}
else
{
dp[j] = dp[j - A[i]] - 1; // 用上了一个第i个硬币
}
}
}
int answer = count_if(dp + 1, dp + 1 + m , bind2nd(greater_equal<int>(), 0)); // 总额0不算在答案内
cout << answer << endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}