Programming學習筆記
網頁
首頁
UVa
POJ
2014年4月30日 星期三
POJ 1276 Cash Machine
題意:
不同價值Dk元的鈔票有Nk張,現在要求用這些鈔票能湊出最接近cash是多少元?
想法:
背包問題,dp[i]=k表示i重量上限的背包最多能裝k價值的東西,題目給的Nk表示該物品的數量,而Dk是重量同時也是價值,這樣去求背包問題。因為這題時間限制,須採用和
POJ 1024
一樣的做法,將Nk件捆成1+2+4+8+16+32+....+left的形式,減低運算次數。
沒有留言:
張貼留言
較新的文章
較舊的文章
首頁
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言