uva 674 Coin Change(完全背包）

题目连接：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;}