0-1背包问题的贪心、动态规划、回溯算法.doc

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.09M 资料格式：doc 举报版权申诉

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第1页.png

第1页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第2页.png

第2页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第3页.png

第3页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第4页.png

第4页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第5页.png

第5页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第6页.png

第6页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第7页.png

第7页 / 共16页

ziluolanzhang-5130246-4744300845157010688.doc.pdf-第8页.png

第8页 / 共16页

文本预览

实验二算法实现二一、实验目的与要求熟悉 C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容: 掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握"0-1"背包问题的三种算法，并分析其优缺点。三、实验题 1. 2. 3. "0-1"背包问题的贪心算法 "0-1"背包问题的动态规划算法 "0-1"背包问题的回溯算法四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序 1、"0-1"背包问题的贪心算法 #include void Sort(int n,float v[],float w[]) //按物品单位重量价值从大到小排序 { 1

float temp,temp1; for(int i=1;i

scanf("%d",&n); float v[20],w[20],c; int x[20]; printf("请输入背包容量:\n"); scanf("%f",&c); printf("请分别输入物品的价值和重量:\n"); printf("%d 个重量:\n",n); for(int k=0;k

for(i=0;ic) //背包容不下该物品时 { } x[i]=0; else // 背包可以装下时 { } x[i]=1; value=value+v[i]; c=c-w[i]; printf("\n 放入背包中的最优值为：%f\n ",value); printf("所有物品在背包的存放情况为(0 表示没有放入，1 表示放入)：\n "); for(i=0;i

} 2、"0-1"背包问题的动态规划 #include int min(int x,int y)//求最小值函数 { } if(xb) return a; else return b; void Knapsack(int v[],int w[],int c,int n,int m[][100])//寻找最优解的值 { int jmax=min(w[n-1]-1,c); for(int j=0;j<=jmax;j++) { 5

m[n-1][j]=0; } for(int j1=w[n-1];j1<=c;j1++) { } m[n-1][j1]=v[n-1]; for(int i=n-2;i>0;i--) { } jmax=min(w[i]-1,c); for(int j2=0;j2<=jmax;j2++) m[i][j2]=m[i+1][j2]; for(int j3=w[i];j3<=c;j3++) { } m[i][j3]=max(m[i+1][j3],m[i+1][j3-w[i]]+v[i]); m[0][c]=m[1][c]; if(c>=w[0])m[0][c]=max(m[0][c],m[1][c-w[0]]+v[0]); } void Traceback(int m[][100],int w[],int c,int n,int x[]) //寻找最优解 { for(int i=0;i

{ } if(m[i][c]==m[i+1][c])x[i]=0; else { } x[i]=1;c=c-w[i]; x[n-1]=m[n-1][c]?1:0; } void main(void) { //初始化 int n; printf("请输入物品个数：\n"); scanf("%d",&n); int c; printf("请输入背包容量：\n"); scanf("%d",&c); int w[20],v[20],m[20][100],x[20]; printf("请输入%d 个物品的重量：\n",n); for(int i=0;i

scanf("%2d",&w[i]); } printf("请输入%d 个物品的价值：\n",n); for(int j=0;j 8

分享到：

赞收藏

资料库

0-1背包问题的贪心、动态规划、回溯算法.doc

相关推荐

课程资源

热门标签

最新资料