姓名：學號：
班級：一、 實驗目的與要求：
熟悉c/c++語言的整合開發環境；
通過本實驗加深對貪心演算法、動態規劃和回溯演算法的理解。
二、 實驗內容：
掌握貪心演算法、動態規劃和回溯演算法的概念和基本思想，分析並掌握"0-1"揹包問題的三種演算法，並分析其優缺點。
三、 實驗程式：
#include""
int n=5;
int w=;
int v=;
int x[5];
int v[6][7];
int c=6;
void main(void)
}//以上構造動態規劃表
j=c;
for(i=n;i>0;i--)
else
x[i]=0;
}printf("動態規劃表如下：\n");
for(i=0;i<6;i++)
printf("\n");
}printf("裝入揹包物品：\n");
for(i=0;i<6;i++)
printf("%4d",x[i]);
printf("\n揹包取得最大值：\n");
printf("%4d\n",v[n][c]);
}三、實驗結果：
四、實驗分析：
這次實驗用到的是動態規劃法，0/1揹包問題用動態規劃法首先要構造動態規劃表，用三個for語句實現；根據動態規劃表每行的最大值變化確定每個元素的裝入與否，逐步確定出裝入揹包的物品，揹包容量的最大值也就是動態規劃表最右下角。在本次實驗中遇到了動態規劃表構造紊亂的狀況，經核查是因陣列的初始位置0混淆成1造成的。
一、 實驗目的與要求：
熟悉c/c++語言的整合開發環境；
通過本實驗加深對貪心演算法、動態規劃和回溯演算法的理解。
二、 實驗內容：
掌握貪心演算法、動態規劃和回溯演算法的概念和基本思想，分析並掌握"0-1"揹包問題的三種演算法，並分析其優缺點。
三、 實驗程式：
#include""
void main(void)
;//物品重量
int v=;//物品價值
int x=;//單位價值初始化
int q[5];
int m,i,j,p,vx,wx,k,ii;
int v=0;//總價值初始化
//計算單位價值
printf("單位價值為：\n");
for(m=0;m<5;m++)
//氣泡排序
for(i=0;i<4;i++)
}printf("\n單位價值降序為：\n");
for(i=0;i<5;i++)
printf("x[%d]=%d\t",i,x[i]);
//裝入揹包
for(i=0;i
}k=i;
if(c!=0)
for(ii=0;ii<=k;ii++)
printf("\n總價值為：%d\t",v);
}四、 實驗結果：
五、 實驗分析：
本次實驗是以貪心演算法解決揹包問題，貪心演算法要求出每個物品的單位價值，根據單位價值降序排列，再依次裝入揹包。當最後乙個物品不能完全裝入時，裝入部分使揹包容量為0。
在本次實驗中，遇到幾個難題：
1． 保證物品按單位價值排列後依然能知道他的原始順序位置，經過幾番思考，決定設定乙個陣列來儲存該物品的原始位置，在冒泡演算法交換時同時交換物品編號；
2． 裝入揹包過程如何保證裝入不完整物品，即揹包剩餘容量不能滿足完全放入下乙個物品。
通過本次試驗又熟悉了冒泡演算法的應用，以及多重for迴圈的應用。
一、 實驗目的與要求：
熟悉c/c++語言的整合開發環境；
通過本實驗加深對貪心演算法、動態規劃和回溯演算法的理解。
二、 實驗內容：
掌握貪心演算法、動態規劃和回溯演算法的概念和基本思想，分析並掌握"0-1"揹包問題的三種演算法，並分析其優缺點。
三、 實驗程式：
#include <>
//定義min、max函式
int min(int a,int b)
int max(int a,int b)
void knapsack(int v[6],int w[6],int c,int n,int m[6][6])//
m[1][c]=m[2][c];
if(c>=w[1])
m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);
}void traceback(int m[6][6],int w[6],int c,int n,int x[6])
x[n]=(m[n][c]!=0)?1:0;
}void main()
; int v1[6]=;
int t[6][6];
int x1[6];
int m=0;
//cout<<"請輸入揹包的容量："< //cin>>c1;
cout<<"0-1揹包如下："< cout<<"物品的重量分別為："< for(int p=1;p<6;p++)
cout< cout< cout<<"物品的價值分別為："< for(int q=1;q<6;q++)
cout< cout< cout<<"揹包的容量為："< cout<<"要選擇的物品是:"< knapsack(v1,w1,c1,n1,t);
//for(int i=1;i<=n1;i++)cout< traceback(t,w1,c1,n1,x1);
for(i=1;i<=n1;i++)
if(x1[i]==1)
四、 實驗結果：
五、 實驗分析：
本次實驗用回溯法解決0/1揹包問題，回溯法首先要建立0/1揹包的解空間樹，然後再回溯得出搜素空間，即解的範圍，然後求出最佳答案。實驗中先構造兩個函式，knapsack列出所有揹包的解空間，traceback對解空間進行搜尋，得出答案。
演算法設計與分析實驗報告 01揹包問題
演算法設計與分析 實驗報告 0 1揹包問題 問題描述 給定n種物品和乙個揹包。物品i的重量是，其價值為，揹包容量為c。問應該如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大？問題分析 0 1揹包問題的可形式化描述為 給定c 0,0,0,要求找出n元0 1向量，使得，而且達到最大。因此0 1揹包...
實驗4用分支限界法實現0 1揹包問題
一 實驗目的 1.熟悉分支限界法的基本原理。2.通過本次實驗加深對分支限界法的理解。二 實驗內容及要求 內容 給定n種物品和乙個揹包。物品i的重量是w，其價值為v，揹包容量為c。問應該如何選擇裝入揹包的物品，使得裝入揹包中物品的總價值最大?要求 使用優先佇列式分支限界法演算法程式設計，求解0 1揹包...
利用動態規劃求解01揹包問題
演算法分析與設計 實驗報告 班級 0209404班 學號 020940410 姓名 楊洲 上機時間 2011 11 7 1 實驗目的與要求 1 掌握動態規劃演算法求解問題的一般特徵和步驟 2 使用動態規劃法程式設計，求解0 1揹包問題。2 實驗題目 利用動態規劃求解0 1揹包問題 3 實驗內容 0 ...