a.c

来自「该源码转自于其它网站」· C语言 代码 · 共 54 行

# include <stdio.h> 
# define N 100 
double limitW,totV,maxV; 
int option[N],cop[N]; 
struct { double weight; 
double value; 
}a[N]; 
int n; 
void find(int i,double tw,double tv) 
{ int k; 
/*考虑物品i包含在当前方案中的可能性*/ 
if (tw+a[i].weight<=limitW) 
{ cop[i]=1; 
if (i<n-1) find(i+1,tw+a[i].weight,tv); 
else 
{ for (k=0;k<n;k++) 
option[k]=cop[k]; 
maxV=tv; 
} 
cop[i]=0; 
} 
/*考虑物品i不包含在当前方案中的可能性*/ 
if (tv-a[i].value>maxV) 
if (i<n-1) find(i+1,tw,tv-a[i].value); 
else 
{ for (k=0;k<n;k++) 
option[k]=cop[k]; 
maxV=tv-a[i].value; 
} 
} 

void main() 
{ int k; 
double w,v; 
printf("输入物品种数\n"); 
scanf("%d",&n); 
printf("输入各物品的重量和价值\n"); 
for (totV=0.0,k=0;k<n;k++) 
{ scanf("%1f%1f",&w,&v); 
a[k].weight=w; 
a[k].value=v; 
totV+=v; 
} 
printf("输入限制重量\n"); 
scanf("%1f",&limitW); 
maxV=0.0; 
for (k=0;k<n;k++) cop[k]=0; 
find(0,0.0,totV); 
for (k=0;k<n;k++) 
if (option[k]) printf("%4d",k+1); 
printf("\n总价值为%.2f\n",maxV); 
}