描述:石頭收藏家小明在徒步登山的時候發(fā)現(xiàn)了一堆美麗的石頭。這些石頭價值不菲，但是都很重，小明自身的力氣有限，一次只能拿他拿得動的一部分。每塊石頭的重量不同，價值也不同。問小明在力所能及的情況下能拿走價值多少的石頭。 說明：小明只能搬運一次。 例如：小明只能拿得動 10 kg，每塊石頭的重量分別為2kg，3kg，5kg，7kg，對應的價值分別為 1萬，5萬，2萬，4萬。小明能拿的是 3kg 以及 7kg 的石頭，價值 9 萬。 輸入 使用分號(;)分隔三組數(shù)據(jù)。 第一組為一個整數(shù)，表示小明一次能搬運的最大重量。 第二組為一個使用逗號(,)分隔的數(shù)組，表示每塊石頭的重量。 第三組為一個使用逗號(,)分隔的數(shù)組，表示每塊石頭的對應的價值。
輸出 一個整數(shù)，表示小明這次能帶回去的石頭的總價。
輸入樣例 10;2,3,5,7;1,5,2,4 輸出樣例 9
動態(tài)規(guī)劃 dp[i,w]表示背包容量為w時，i個物品最優(yōu)解的總價值,可得到以下推導公式 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個物品時,所獲得的最優(yōu)解, dp[i-1,w]表示不選擇第i個物品時的最優(yōu)解.
實現(xiàn)時dp[i,w]可以用一個二維數(shù)組來實現(xiàn),為了壓縮空間,也可以使用一維數(shù)組.
二維數(shù)組下的求解順序，物品數(shù)1—>n, 背包容量1—>w。要使用一維數(shù)組，背包容量要采用倒序，即w—>1, 只有這樣對于方程dp[j] = max{( dp[j], dp (j-w[i] ) + v[i] }，才能達到等式左邊才表示i,而等式右邊表示i-1的效果。
代碼
public static int solve(int n ,int w, int[] weight, int[] value){ //動態(tài)規(guī)劃結(jié)果數(shù)組 int[] dp=new int[w+1]; //最優(yōu)值dp[j]=max{dp[j], dp[j-w[i]]+vi} , 其中0<=j<=w; for(int i=0;i<n;i++){ for(int j=w;j>=weight[i];j--){ if(dp[j-weight[i]]+value[i]>dp[j]){ dp[j]=dp[j-weight[i]]+value[i]; } } } return dp[w]; }參考: http://blog.csdn.net/sj13051180/article/details/6687674
新聞熱點
疑難解答
