uva 674 Coin Change(完全背包）

題目大意：有5種硬幣， 面值分別為1、5、10、25、50，現在給出金額，問可以用多少種方式組成該面值。   解題思路：每種硬幣都有無限個，所以是典型的完全背包， 一開始寫的時候沒有考慮到面值的重復問題， 打表的時候將金額值逐一去計算， 但又使用到cnt[i] += cnt[i - sex[j]],  然後導致有些組成方式重復考慮進去（這種只適用50以內的， 不會造成面值的的重復考慮， 比如 100， 在sex[j] == 25時， cnt[100] += cnt[75], 但是75裡面的組成方式裡有可以用面值為50去組成的方案， 所以等下計算sex[j] == 50的時候就重復計算了） 正確的做法是cnt[i] += low(cnt[i - sex[j]])   表示說cnt[i - sex[j]] 中用面值小於等於sex[j]的組成方式種類。寫法代碼中給出。    

#include <stdio.h>  
#include <string.h>  
const int N = 7500;  
const int sex[] = {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 = sex[i]; j < N; j++)  
        cnt[j] += cnt[j - sex[i]];  
    }  
}  
  
int main() {  
    Init();  
    while (scanf("%d", &n) == 1) {  
    printf("%d\n", cnt[n]);  
    }  
    return 0;  
}