[動態規劃]USACO Jan07 Bronze:Making Change解題報告

【題目描述】

Poor Bessie has taken a job in the convenience store located just over the border in Slobbovia. Slobbovians use different coinages than the USA; their coin values change day-by-day!
Help Bessie make optimal change for Slobbovian shoppers. You will need to create C (1 ≤ C ≤ 1000) cents of change using N (1 ≤ N ≤ 10) coins of various values. All test cases will be solvable using the supplied coins.
If 5 coins of values 50, 25, 10, 5, and 1 were available, Bessie would make optimum change (minimal coins) of 93 cents by using 1 x 50, 1 x 25, 1 x 10, 1 x 5, and 3 x 1 coins (a total of 7 coins).
How hard could it be? The final two test cases will be challenging.
Input

• Line 1: Two space-separate integers: C and N

• Lines 2..N + 1: Each line contains a single unique integer that is a coin value that can be used to create change

Output

• Line 1: A single integer that is the minimum number of coins to create C cents

Sample Input

93 5
25
50
10
1
5

Sample Output

7 

【分析】
（官方題解：http://ace.delos.com/TESTDATA/JAN07.change.htm）
（官方數據：http://ace.delos.com/TESTDATA/change.zip）

這是一道動態規劃題，如果用貪心做，可以過8組測試數據，最後兩組會錯掉的。（這數據也太弱了吧。）

[貪心做法]
先對所有的硬幣面值進行快速排序，然後每次用C減去面值最大的那種硬幣，直到C小於硬幣的最大面值，然後更新硬幣的最大面值......，直到C被減到0為止，輸出C被減去的次數即可。
這種算法可以過8組測試數據！


[動態規劃做法]
由於每種硬幣沒有使用次數的限制，所以每種狀態對其以前狀態沒有影響，所以可用DP來求解。

狀態設定 
     F[i]： 拼出i元的最小硬幣數。
     M[1~N]：1~N中硬幣的面值。
邊界條件
    F[0]=0
狀態轉移方程
    F[i]=Min{F[i-M[k]+1} (i-M[k]>=0, 1<=k<=N)
目標結果
    F[N]


【我的代碼】
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define Min(a,b) a<=b?a:b
using namespace std;
int T;
int N;
int C[11];
int F[1001];

void init()
{
    cin>>T>>N;
    for (int i=1;i<=N;i++)
        cin>>C[i];
    return;
}

void dp()
{
    F[0]=0;
    for (int i=1;i<=T;i++)
    {
        F[i]=10000;
        for (int j=1;j<=N;j++)
        {
            if(i-C[j]>=0)
                F[i]=Min(F[i],F[i-C[j]]+1);
        }
    }
    cout<<F[T]<<endl;
}

int main()
{
    freopen("change.in","r",stdin);
    freopen("change.out","w",stdout);
    init();
    dp();
    return 0;
}


正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	273 KB	0
2	正确	10	0.000 s	273 KB	0
3	正确	10	0.000 s	273 KB	0
4	正确	10	0.000 s	273 KB	0
5	正确	10	0.000 s	273 KB	0
6	正确	10	0.000 s	273 KB	0
7	正确	10	0.000 s	273 KB	0
8	正确	10	0.000 s	273 KB	0
9	正确	10	0.000 s	273 KB	0
10	正确	10	0.000 s	273 KB	0

运行完成
运行时间 0.003 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!