問題描述
設有n種不同面值的硬幣，各硬幣的面值存于數(shù)組T[1:n]中。現(xiàn)要用這些面值的硬幣來找錢，可以實用的各種面值的硬幣個數(shù)不限。當只用硬幣面值T[1],T[2],…,T[i]時，可找出錢數(shù)j的最少硬幣個數(shù)記為C(i,j)。若只用這些硬幣面值，找不出錢數(shù)j時，記C(i,j)=∞。
編程任務
設計一個動態(tài)規(guī)劃算法，對1≤j≤L，計算出所有的C( n,j )。算法中只允許實用一個長度為L的數(shù)組。用L和n作為變量來表示算法的計算時間復雜性
數(shù)據(jù)輸入
由文件input.txt提供輸入數(shù)據(jù)。文件的第1行中有1個正整數(shù)n（n<=13），表示有n種硬幣可選。接下來的一行是每種硬幣的面值。由用戶輸入待找錢數(shù)j。
結(jié)果輸出
程序運行結(jié)束時，將計算出的所需最少硬幣個數(shù)輸出到文件output.txt中。
標簽：
上傳時間：
2016-07-28
上傳用戶：yangbo69
