動態規劃法解

2011級3班張思源

動態規劃演算法原理：將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解；對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來。為了不去求解相同的子問題，引入乙個陣列，把所有子問題的解存於該陣列中，這就是動態規劃所採用的基本方法。

動態規劃採用由下至上計算策略。

一、問題描述與分析

動態規劃法解0-1揹包問題：某商店有n個物品，第i個物品價值為vi，重量(或稱權值)為wi，其中vi和wi為非負數，揹包的容量為w（w為一非負數）。目標是如何選擇裝入揹包的物品，使裝入揹包的物品總價值最大，所選商品的乙個可行解即所選商品的序列如何揹包問題與0-1 揹包問題的不同點在於，在選擇物品裝入揹包時，可以只選擇物品的一部分，而不一定要選擇物品的全部。

二、演算法設計（演算法步驟）

設0/1揹包問題的最優值為m( i, j )，即揹包容量是j，可選擇物品為i,i+1,…,n時0/1揹包問題的最優值。由0/1揹包問題的最優子結構性質，可以建立計算m( i, j )的遞迴式如下：

maxm( i, j )=

m(i+1,j)

m(n,j)=

0三、演算法實現

程式源**：

#include <>

#include<>

int min(int w, int c)

int max(int w, int c)

void knapsack(int v, int w, int** m, int c, int n) //求最優值

int traceback(int x, int w, int** m, int c, int n) //回代，求最優解

int main()

int n, c;

int **m;

cout <<0-1揹包問題程式<< endl;

cout << "請輸入物品個數: ";

cin >> n ;

cout << endl << "請輸入揹包的承重：";

cin >> c;

int *v = new int[n+1];

cout << endl << "請輸入每個物品的價值 (v[i]): " << endl;

for(int i = 1; i <= n; i++)

cin >> v[i];

int *w = new int[n+1];

cout << endl << "請輸入每個物品的重量 (w[i]): " << endl;

for(int j = 1; j <= n; j++)

cin >> w[j];

int *x = new int[n+1];

m = new int* [n+1動態的分配二維陣列

for(int p = 0; p < n+1; p++)

m[p] = new int[c+1];

knapsack (v, w, m, c, n);

traceback(x, w, m, c, n);

system("pause");

}程式執行截圖：

四、演算法分析與改進

動態規劃法解

揹包問題的動態規劃法

最大欄位和問題動態規劃法

備忘錄方法動態規劃法的變形

動態規劃法解

揹包問題的動態規劃法

最大欄位和問題動態規劃法

備忘錄方法 動態規劃法的變形

相關推薦

備忘錄方法動態規劃法的變形