問題描述
設(shè)有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)=∞。
編程任務(wù)
設(shè)計一個動態(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