一个背包问题，因为w == v 的特性，可以用01背包解决，设置数组cnt来记录硬币使用次数
依次运行初始化一次dp数组，然后将所以硬币遍历一次，，先设置目标价格，再看这个价格是否可以达到（用下标表示价格）。
转载自http://blog.csdn.net/u012762625/article/details/43485973；
里面还有两种更高级的解决办法，有空再看看
#include <stdio.h> #include <string.h> int dp[100005], v[105],num[105], cnt[100005]; int main() { int n, m, i, j; while(scanf("%d%d", &n, &m) != EOF && n+m) { int ans = 0; memset(dp, 0, sizeof(dp)), dp[0] = 1; for (i = 0; i < n; i ++) { scanf("%d", v + i); } for (i = 0; i < n; i ++) { scanf("%d", num + i); } for (i = 0; i < n; i ++) { memset(cnt, 0, sizeof(cnt)); for (j = v[i]; j <= m; j ++) { if(dp[j-v[i]] == 1 && dp[j] == 0 && cnt[j-v[i]] < num[i]) { cnt[j] = cnt[j-v[i]] + 1; dp[j] = 1; ans ++; } } } printf("%d\n", ans); } return 0; }