動態規劃的用法——01背包問題 · 算法程序設計

動態規劃的用法——01背包問題 <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">問題主題：著名的01背包問題</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">問題描述：有n個重量和價值分別為wi、vi的物品，現在要從這些物品中選出總重量不超過W的物品，求所有挑選方案中的價值最大值。限制條件：1<=N<=1001<=wi?、vi<=1001<=wi<=10000</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">樣例：輸入N=4W[N]?=?{2,?1,?3,?2}V[N]?=?{3,?2,?4,?2}輸出W?=?5(選擇0，1，3號)</td></tr></tbody></table> ### 【解法一】 ### 解題分析： ???用普通的遞歸方法，對每個物品是否放入背包進行搜索 ### 程序實現: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="163214" snippet_file_name="blog_20140119_1_8512058" name="code" class="cpp">#include <stdio.h> #include <tchar.h> #include <queue> #include "iostream" using namespace std; const int N = 4; const int W = 5; int weight[N] = {2, 1, 3, 2}; int value[N] = {3, 2, 4, 2}; int solve(int i, int residue) { int result = 0; if(i >= N) return result; if(weight[i] > residue) result = solve(i+1, residue); else { result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]); } } int main() { int result = solve(0, W); cout << result << endl; return 0; }</pre> ?</td></tr></tbody></table> **** ### 【解法二】 ### 解題分析： ???用記錄結果再利用的動態規劃的方法，上面用遞歸的方法有很多重復的計算，效率不高。我們可以記錄每一次的計算結果，下次要用時再直接去取，以提高效率 ### 程序實現: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="163214" snippet_file_name="blog_20140119_2_8544295" name="code" class="cpp">#include <stdio.h> #include <tchar.h> #include <queue> #include "iostream" using namespace std; const int N = 4; const int W = 5; int weight[N] = {2, 1, 3, 2}; int value[N] = {3, 2, 4, 2}; int record[N][W]; void init() { for(int i = 0; i < N; i ++) { for(int j = 0; j < W; j ++) { record[i][j] = -1; } } } int solve(int i, int residue) { if(-1 != record[i][residue]) return record[i][residue]; int result = 0; if(i >= N) return result; if(weight[i] > residue) { record[i + 1][residue] = solve(i+1, residue); } else { result = max(solve(i+1, residue), solve(i+1, residue-weight[i]) + value[i]); } return record[i + 1][residue] = result; } int main() { init(); int result = solve(0, W); cout << result << endl; return 0; }</pre> </td></tr></tbody></table> **Java** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="163214" snippet_file_name="blog_20140119_3_2862694" name="code" class="java">package greed; /** * User: luoweifu * Date: 14-1-21 * Time: 下午5:13 */ public class Knapsack { private int maxWeight; private int[][] record; private Stuff[] stuffs; public Knapsack(Stuff[] stuffs, int maxWeight) { this.stuffs = stuffs; this.maxWeight = maxWeight; int n = stuffs.length + 1; int m = maxWeight+1; record = new int[n][m]; for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j ++) { record[i][j] = -1; } } } public int solve(int i, int residue) { if(record[i][residue] > 0) { return record[i][residue]; } int result; if(i >= stuffs.length) { return 0; } if(stuffs[i].getWeight() > residue) { result = solve(i + 1, residue); } else { result = Math.max(solve(i + 1, residue), solve(i + 1, residue - stuffs[i].getWeight()) + stuffs[i].getValue()); } record[i][residue] = result; return result; } public static void main(String args[]) { Stuff stuffs[] = { new Stuff(2, 3), new Stuff(1, 2), new Stuff(3, 4), new Stuff(2, 2) }; Knapsack knapsack = new Knapsack(stuffs, 5); int result = knapsack.solve(0, 5); System.out.println(result); } } class Stuff{ private int weight; private int value; public Stuff(int weight, int value) { this.weight = weight; this.value = value; } int getWeight() { return weight; } void setWeight(int weight) { this.weight = weight; } int getValue() { return value; } void setValue(int value) { this.value = value; } }</pre> <pre/></td></tr></tbody></table> **** ### 算法復雜度： ???時間復雜度O(NW)