uva 674 Coin Change(完全背包）

题目大意：有5种硬币，面值分别为1、5、10、25、50，现在给出金额，问可以用多少种方式组成该面值。

解题思路：每种硬币都有无限个，所以是典型的完全背包，一开始写的时候没有考虑到面值的重复问题，打表的时候将金额值逐一去计算，但又使用到cnt[i] += cnt[i - 易做图[j]], 然后导致有些组成方式重复考虑进去（这种只适用50以内的，不会造成面值的的重复考虑，比如 100，在易做图[j] == 25时， cnt[100] += cnt[75], 但是75里面的组成方式里有可以用面值为50去组成的方案，所以等下计算易做图[j] == 50的时候就重复计算了）

正确的做法是cnt[i] += low(cnt[i - 易做图[j]]) 表示说cnt[i - 易做图[j]] 中用面值小于等于易做图[j]的组成方式种类。写法代码中给出。

#include <stdio.h>  
#include <string.h>  
const int N = 7500;  
const int 易做图[] = {1, 5, 10, 25, 50};  
  
int n, cnt[N], t;  
  
void Init() {  
    memset(cnt, 0, sizeof(cnt));  
    cnt[0] = 1;  
    for (int i = 0; i < 5; i++) {  
    for (int j = 易做图[i]; j < N; j++)  
        cnt[j] += cnt[j - 易做图[i]];  
    }  
}  
  
int main() {  
    Init();  
    while (scanf("%d", &n) == 1) {  
    printf("%d\n", cnt[n]);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,