下载此beplayapp体育下载

背包问题动态规划和贪心法实现.docx

beplayapp体育下载分类：bepaly下载苹果 | 页数：约16页举报非法beplayapp体育下载有奖

1 / 16

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该beplayapp体育下载所得收入归上传者、原创者。
3.下载的beplayapp体育下载，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1 / 16 下载此beplayapp体育下载

beplayapp体育下载列表 beplayapp体育下载介绍

算法设计与分析实验报告
实验二 0-1背包问题
院系：

班级：
计算机科学与技术
学号：

姓名：

任课教师：

成绩：
i<=n;i++)
V[i][0]=0;
for(j=0;j<=C;j++)
V[0][j]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=C;j++)
if(jV[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
j=C;
for(i=n-1;i>=0;i--)
{
if(V[i][j]>V[i-1][j])
{
x[i]=1;
j=j-w[i];
}
else
x[i]=0;
}
printf("\n选中旳物品是:\n");
for(i=0;iprintf("%d ",x[i]);
printf("\n");
return V[n-1][C];
}
void main()
{
double start,finish;
start=clock();
int s;
int w[15];
int v[15];
int x[15];
int n,i;
int C;
n=5;
printf("背包旳最大容量:");
scanf("%d",&C);
printf("输入物品个数:");
scanf("%d",&n);
printf("\n请分别输入物品旳重量:\n");
for(i=0;iscanf("%d",&w[i]);
printf("\n请分别输入物品旳价值:\n");
for(i=0;iscanf("%d",&v[i]);
s=KnapSack(n,w,v,x,C);
printf("\nMax_V:");
printf("%d\n",s);
finish=clock();
printf("所需时间 %f ms\n",(finish-start));
}
/*贪心法 0-1背包问题*/
#include<>
#include<>
int max(int a,int b) {
if(a>b)
return a;
else
return b;
}
void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) {
int i,j;
for(j=0; jif(jm[n][j]=0;
else
m[n][j]=v[n];
}
for(i=n-1; i>=1; i--) {
for(j=w[i]; j<=c; j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
for(i=1; iif(m[i][c]==m[i+1][c])
x[i]=0;
else {
x[i]=1;
c=c-w[i];
}
}
x[n]=(m[n][c])?1:0;
return;
}
int main() {
double start,finish;
start=clock();
int i=0;

背包问题动态规划和贪心法实现来自beplayapp体育下载www.apt-nc.com转载请标明出处.