網頁

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的形式,減低運算次數。