背包算法.cpp

0、1背包算法

#include<stdio.h> 
#define N 100 

double limitW,totV=0,maxv=0; 

int option[N],cop[N],n,k; 

struct 
{ 
double weight; 
double value; 
}a[N]; 

void find(int i,double tw,double tv) 
{ 
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; 
} 

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() 
{ 
printf("输入物品种数:"); 
scanf("%d",&n); 

printf("\n输入各物品的重量和价值:"); 
for(k=0; k<n; totV+=a[k].value,k++) 
scanf("%lf%lf",&a[k].weight,&a[k].value); 

printf("\n输入限制重量:"); 
scanf("%lf",&limitW); 

for(k=0;k<n;k++) 
cop[k]=0; 

find(0,0,totV); 

for(k=0;k<n;k++) 
if(option[k]) 
printf("%4d",k+1); 

printf("\n总价值为:%.3f\n",maxv); 
}