贪心算法0-1背包问题(算法实验代码)

2022-07-14 01:11:20 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《贪心算法0-1背包问题(算法实验代码)》，欢迎阅读！
算法,贪心,背包,实验,代码

实验三、0-1背包问题（贪心算法）

实验代码：

#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;j {

if(j m[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;i {

if(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() {

int i=0; int n=7;

int w[]={0,2,3,5,7,1,4,1}; int v[]={0,10,5,15,7,6,18,3}; int x[]={0,0,0,0,0,0,0,0};

1 / 2

printf("物品总数为：7\n");

printf("物品重量和价值分别为：\n"); printf("\n重量价值 \n"); for (i=1;i<=n;i++)

printf("%d %d \n",w[i],v[i]); int m=15;

int array[8][100]={0};

Knapsack(v,w,x,m,7,array);

printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: "); for(i=1;i<=n;i++) {

if(i==1)

printf("%d",x[i]); else

printf(" %d",x[i]); }

printf("\n"); return 0; }

测试截图为：

2 / 2

本文来源：https://www.dywdw.cn/0735ee4a2e3f5727a5e9620f.html