演算法分析與設計
實驗報告
班級： 0209404班
學號： 020940410
姓名： 楊洲
上機時間： 2011-11-7
1、實驗目的與要求：
1、掌握動態規劃演算法求解問題的一般特徵和步驟；
2、使用動態規劃法程式設計，求解0/1揹包問題。
2、實驗題目：利用動態規劃求解0-1揹包問題
3、實驗內容：
0-1揹包問題(knapsack problem)， 某商店有n個物品，第i個物品價值為vi，重量(或稱權值)為wi，其中vi和wi為非負數, 揹包的容量為w，w為一非負數。目標是如何選擇裝入揹包的物品，使裝入揹包的物品總價值最大，所選商品的乙個可行解即所選商品的序列如何？揹包問題與0-1揹包問題的不同點在於，在選擇物品裝入揹包時，可以只選擇物品的一部分，而不一定要選擇物品的全部。
4、問題描述：
給定n和物品和一人揹包，物品i的重量是wi，其價值為vi，問如何選擇裝入揹包的物品，使得裝入揹包的物品的總價值最大？
舉例:若商店一共有5類商品，重量分別為：3，4，7，8，9
價值分別為：4，5，10，11，13
則：所選商品的最大價值為24
所選商品的乙個序列為：0 0 0 1 1
5、問題分析與演算法設計
動態規劃原理：動態規劃是一種將問題例項分解為更小的、相似的子問題，並儲存子問題的解而避免計算重複的子問題，以解決最優化問題的演算法策略。
動態規劃法所針對的問題有乙個顯著的特徵，即它所對應的子問題樹中的子問題呈現大量的重複。動態規劃法的關鍵就在於，對於重複出現的子問題，只在第一次遇到時加以求解，並把答案儲存起來，讓以後再遇到時直接引用，不必重新求解。
6、實驗結果及分析
7、實驗總結
8、程式**
#include
int c[10][100];/*對應每種情況的最大價值*/
int knapsack(int m,int n)
x[1]=c[1][m]?1:0;
for(i=1;i<=n;i++)
printf("%3d",x[i]);
}int main()
實驗七動態規劃求解揹包問題
實驗目的 1 以0 1揹包問題為例，掌握動態規劃演算法的基本設計策略 2 掌握並實現求解0 1揹包問題的動態規劃演算法 3 分析實驗結果。實驗環境 計算機 c語言程式設計環境 實驗學時 2學時實驗內容與步驟 1.理解0 1揹包問題 0 1揹包問題的描述 已知有n個物品和乙個承重為m的揹包，物品i的重...
編寫程式,用動態規劃法求解0 1揹包問題
要求 編寫程式，用動態規劃法求解0 1揹包問題。一 實驗目的與要求 1 明確0 1揹包問題的概念 2 利用動態規劃解決0 1揹包問題問題 二 實驗題 0 1揹包問題 knapsack problem 某商店有n個物品，第i個物品價值為vi，重量 或稱權值 為wi，其中vi和wi為非負數,揹包的容量為...
揹包問題的動態規劃法
揹包問題 在m件物品取出若干件放在空間為w的揹包裡，每件物品的重量為w1，w 2 wn，與之相對應的價值為p1,p2 pn。求出獲得最大價值的方案。注意 在本題中，所有的重量值均為整數。演算法分析 對於揹包問題，通常的處理方法是搜尋。用遞迴來完成搜尋，演算法設計如下 function make i ...