要求：編寫程式，用動態規劃法求解0—1揹包問題。
一、 實驗目的與要求
1、明確0-1揹包問題的概念
2、利用動態規劃解決0-1揹包問題問題
二、實驗題：
0-1揹包問題(knapsack problem)， 某商店有n個物品，第i個物品價值為vi，重量(或稱權值)為wi，其中vi和wi為非負數, 揹包的容量為w，w為一非負數。目標是如何選擇裝入揹包的物品， 使裝入揹包的物品總價值最大，所選商品的乙個可行解即所選商品的序列如何？揹包問題與0-1揹包問題的不同點在於，在選擇物品裝入揹包時，可以只選擇物品的一部分， 而不一定要選擇物品的全部。
可將這個問題形式描述如下：
約束條件為：
舉例:若商店一共有5類商品，重量分別為：3，4，7，8，9
價值分別為：4，5，10，11，13
則：所選商品的最大價值為24
所選商品的乙個序列為：0 0 0 1 1
三、實驗**
#include <>
#include<>
#include<>
int min(int w,int c)
int max(int w,int c)
void knapsack(int v,int w,int c,int n,int**m) //求最優值
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
cout<<"最優值：" int traceback(int **m,int w,int c,int n,int x) //回代，求最優解 x[n]=(m[n][c])?1:0; for(int y=1;y<=n;y++) cout } void main() knapsack(v,w,c,n,m); traceback(m,w,c,n,x); }四、實驗結果 2011級3班張思源 動態規劃演算法原理 將待求解的問題分解成若干個相互聯絡的子問題，先求解子問題，然後從這些子問題的解得到原問題的解 對於重複出現的子問題，只在第一次遇到的時候對它進行求解，並把答案儲存起來。為了不去求解相同的子問題，引入乙個陣列，把所有子問題的解存於該陣列中，這就是動態規劃所採用... 揹包問題 在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w 2 wn，與之相對應的價值為p1,p2 pn。求出獲得最大價值的方案。注意 在本題中，所有的重量值均為整數。演算法分析 對於揹包問題，通常的處理方法是搜尋。用遞迴來完成搜尋，演算法設計如下 function make i ... 淮海工學院計算機工程學院 實驗報告書 課程名 演算法分析與設計 題目 實驗2 動態規劃演算法 最大子段和問題 班級軟體081班 學號110831116 姓名陳點點 實驗2 動態規劃演算法 實驗目的和要求 1 深刻掌握動態規劃法的設計思想並能熟練運用 2 理解這樣乙個觀點 同樣的問題可以用不同的方法解...動態規劃法解
揹包問題的動態規劃法
最大欄位和問題動態規劃法