問題描述

描述:石頭收藏家小明在徒步登山的時(shí)候發(fā)現(xiàn)了一堆美麗的石頭。這些石頭價(jià)值不菲，但是都很重，小明自身的力氣有限，一次只能拿他拿得動(dòng)的一部分。每塊石頭的重量不同，價(jià)值也不同。問小明在力所能及的情況下能拿走價(jià)值多少的石頭。 說明：小明只能搬運(yùn)一次。 例如：小明只能拿得動(dòng) 10 kg，每塊石頭的重量分別為2kg，3kg，5kg，7kg，對(duì)應(yīng)的價(jià)值分別為 1萬，5萬，2萬，4萬。小明能拿的是 3kg 以及 7kg 的石頭，價(jià)值 9 萬。 輸入 使用分號(hào)(;)分隔三組數(shù)據(jù)。 第一組為一個(gè)整數(shù)，表示小明一次能搬運(yùn)的最大重量。 第二組為一個(gè)使用逗號(hào)(,)分隔的數(shù)組，表示每塊石頭的重量。 第三組為一個(gè)使用逗號(hào)(,)分隔的數(shù)組，表示每塊石頭的對(duì)應(yīng)的價(jià)值。

輸出 一個(gè)整數(shù)，表示小明這次能帶回去的石頭的總價(jià)。

輸入樣例 10;2,3,5,7;1,5,2,4 輸出樣例 9

思路

動(dòng)態(tài)規(guī)劃 dp[i,w]表示背包容量為w時(shí)，i個(gè)物品最優(yōu)解的總價(jià)值,可得到以下推導(dǎo)公式 i=0或w=0, dp[i,w]=0; wi>w, dp[i,w]=dp[i-1,w]; i>0且wi<=w, dp[i,w]=max{dp[i-1,w-wi}+vi,dp[i-1,w]} 其中dp[i-1,w-wi}+vi表示 選擇第i個(gè)物品時(shí),所獲得的最優(yōu)解, dp[i-1,w]表示不選擇第i個(gè)物品時(shí)的最優(yōu)解.

實(shí)現(xiàn)時(shí)dp[i,w]可以用一個(gè)二維數(shù)組來實(shí)現(xiàn),為了壓縮空間,也可以使用一維數(shù)組.

二維數(shù)組下的求解順序，物品數(shù)1—>n, 背包容量1—>w。要使用一維數(shù)組，背包容量要采用倒序，即w—>1, 只有這樣對(duì)于方程dp[j] = max{( dp[j], dp (j-w[i] ) + v[i] }，才能達(dá)到等式左邊才表示i,而等式右邊表示i-1的效果。

代碼

參考: http://blog.csdn.net/sj13051180/article/details/6687674