演算法設計與分析實驗報告 01揹包問題

演算法設計與分析

實驗報告

—0/1揹包問題

-【問題描述】

給定n種物品和乙個揹包。物品i的重量是，其價值為，揹包容量為c。問應該如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大？

【問題分析】

0/1揹包問題的可形式化描述為：給定c>0, >0, >0, ，要求找出n元0/1向量，使得，而且達到最大。因此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<>

#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) //回代，求最優解

void main()

【執行結果】

演算法實驗報告01揹包問題

姓名 學號 班級 一 實驗目的與要求 熟悉c c 語言的整合開發環境 通過本實驗加深對貪心演算法 動態規劃和回溯演算法的理解。二 實驗內容 掌握貪心演算法 動態規劃和回溯演算法的概念和基本思想，分析並掌握 0 1 揹包問題的三種演算法，並分析其優缺點。三 實驗程式 include int n 5 i...

演算法分析與設計實驗報告格式

班級姓名 學號名稱 實驗一遞迴與分治 一 實驗目的與要求 正文宋體五號字，段前段後0行，行間距1行二 實驗內容 1 實驗1 1 1 問題描述 正文宋體五號字，段前段後0行，行間距1行 2 演算法思想和流程 可以用自然語言 偽 或流程圖等方式 正文宋體五號字，段前段後0行，行間距1行 3 源 正文宋體...

wireshark抓包分析實驗報告

若惜年1 實驗目的 1.學習安裝使用wireshark軟體，能在電腦上抓包。2.對抓出包進行分析，分析得到的報文，並與學習到的知識相互印證。2 實驗內容 使用抓包軟體抓取http協議通訊的網路資料和dns通訊的網路資料，分析對應的http tcp ip協議和dns udp ip協議。三 實驗正文 i...