題目
給定兩個長度都為N的陣列weights和values，weights[i]和values[i]分別代表i號物品的重量和價值，給定一個正數bag，表示一個載重bag的袋子，你裝的物品不能超過這個重量，回傳你能裝下最多的價值是多少?
該題暴力解法和詳細分析程序請參考這篇博客——暴力遞回——從左往右的嘗試模型2，背包問題，
很明顯，這個題暴力解的時候也會有大量重復計算，請看下圖：
我們跳過記憶化搜索的階段，直接來改成經典的動態規劃，可以先參考這篇文章——從暴力遞回到動態規劃，記憶化搜索，這篇文章詳細分析了加快取的動態規劃（記憶化搜索）和經典動態規劃的改法，
暴力遞回的程序就是動態轉義方程，并且改動態規劃只需依照暴力遞回的程序來改，跟題意已經解耦了，
所以這里直接貼上這個題經典的暴力解法：
public static int process2(int[] w,int[] v,int index,int rest) {
if(rest<0) {
return -1;
}
if(index==w.length) {
return 0;
}
int p1=process2(w, v, index+1, rest);
int p2next=process2(w, v, index+1, rest-w[index]);
int p2=-1;
if(p2next!=-1) {
p2=p2next+v[index];
}
return Math.max(p1, p2);
}
public static int maxValue2(int[] w,int[] v,int bag) {
if(w==null || v==null || w.length!=v.length || w.length==0) {
return 0;
}
return process2(w, v, 0, bag);
}
很明顯，可變引數只有index和rest，所以是一張二維表，
1）rest<0，所以rest左側區域無效；
if(rest<0) {
return -1;
}
2）index==w.length，所以第5行全是0；
if(index==w.length) {
return 0;
}
3）除此以外，上一行總是依賴下一行；并且在每一行都是從左往右開始填；
for(int index=N-1; index>=0; index--) {
for(int rest=0; rest<=bag; rest++) {
int p1=dp[index+1][rest];
int p2=-1;
if(rest-w[index]>0) {
p2=v[index]+dp[index+1][rest-w[index]];
}
dp[index][rest]=Math.max(p1, p2);
}
}
4）回傳 dp[0][bag]，就是結果，
return process2(w, v, 0, bag);
完整代碼：
package com.harrison.class13;
public class Code03_Knapsack {
public static int process2(int[] w,int[] v,int index,int rest) {
if(rest<0) {
return -1;
}
if(index==w.length) {
return 0;
}
int p1=process2(w, v, index+1, rest);
int p2next=process2(w, v, index+1, rest-w[index]);
int p2=-1;
if(p2next!=-1) {
p2=p2next+v[index];
}
return Math.max(p1, p2);
}
public static int maxValue2(int[] w,int[] v,int bag) {
if(w==null || v==null || w.length!=v.length || w.length==0) {
return 0;
}
return process2(w, v, 0, bag);
}
public static int dpway(int[] w,int[] v,int bag) {
int N=w.length;
int[][] dp=new int[N+1][bag+1];
// 因為Java中，陣列初始化默認全是0，所以base case2可以不用特意初始化為0
for(int index=N-1; index>=0; index--) {
for(int rest=0; rest<=bag; rest++) {
int p1=dp[index+1][rest];
int p2=-1;
if(rest-w[index]>=0) {
p2=v[index]+dp[index+1][rest-w[index]];
}
dp[index][rest]=Math.max(p1, p2);
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] w = { 3, 2, 4, 7, 3, 1, 7 };
int[] v = { 5, 6, 3, 19, 12, 4, 2 };
int bag=15;
System.out.println(maxValue2(w, v, bag));
System.out.println(dpway(w, v, bag));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/397414.html
標籤：其他
上一篇：在InternetExplorer的VBAExcel中更改Feature_Browser_Emulation
下一篇：從暴力遞回到動態規劃，記憶化搜索