實驗目的
1）以0/1揹包問題為例，掌握動態規劃演算法的基本設計策略；
2）掌握並實現求解0/1揹包問題的動態規劃演算法；
3) 分析實驗結果。
實驗環境
計算機、c語言程式設計環境
實驗學時
2學時實驗內容與步驟
1. 理解0/1揹包問題
0/1揹包問題的描述：已知有n個物品和乙個承重為m的揹包，物品i的重量為wi、價值為pi。現在的問題是：
如果乙個物品不能被分割以後部分放進揹包，那麼該如何裝包，才能使揹包中物品的價值之和為最大？這個問題可形式化地表述如下：
極大化目標函式
約束條件：
2. 準備實驗資料
確定物品數目n的值，確定各物品的重量（取正整數）和價值；
確定揹包的承重值m（取正整數）。
3. 實現動態規劃演算法
要求：實現mfknapsack演算法。
輸入：引數i（初次呼叫時為物品總數n），j（初次呼叫時為空包承重m）；全域性變數：物品重量weights[1..n]，價值values[1..n]；
輸出：這i個物品的最優子集的價值。
演算法 mfknapsack(i, j)（偽碼）：
// 另有全域性變數v[0..n, 0..m]存放已經解決的子問題的結果；v初始化：v[0,*]=0、v[*,0]=0，其他元素值初始化為負數。
if v[i,j] < 0 // 此問題還沒有解
if j < weights[i]
value mfknapsack(i-1, j)
else
value max
v[i,j] value
return v[i,j]
4. 修改以上演算法，以輸出最大裝包價值對應的那些裝包物品。
實驗報告：
實驗報告應包括以下內容：
（1）題目；
（2）演算法的基本思想描述；
（3）程式流程圖；
（4）給出實驗內容4所要求的演算法偽碼或程式清單；
（5）實驗分析：分析演算法效率；
（6）說明本次除錯實驗的心得體會、經驗等。如果程式未通過，應分析其原因。
利用動態規劃求解01揹包問題
演算法分析與設計 實驗報告 班級 0209404班 學號 020940410 姓名 楊洲 上機時間 2011 11 7 1 實驗目的與要求 1 掌握動態規劃演算法求解問題的一般特徵和步驟 2 使用動態規劃法程式設計，求解0 1揹包問題。2 實驗題目 利用動態規劃求解0 1揹包問題 3 實驗內容 0 ...
編寫程式,用動態規劃法求解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 ...