递归法01背包问题.cpp

算法设计与分析的经典程序

#include <stdio.h>
#define N 100
double limitweight,
totvalue,
maxvalue;
int option[N],
cop[N];
struct{
double weight;
double value;}a[N];
int n;
void find(int i,double tw,double tv)
{int k;
if (tw+a[i].weight <= limitweight){
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];
	maxvalue = tv;
}
cop[i] = 0;
}
if(tv-a[i].value>maxvalue)
	if (i<n-1)    find(i+1,tw,tv-a[i].value);
	else {for ( k=0;k<n;k++) 
		option[k] =cop[k];
		maxvalue = tv-a[i].value;
  }
}
void main()
{int k;
double w,v;
printf("输入物品种数\n");
scanf("%d",&n);
printf("输入各物品的重量和价值\n");
for (totvalue=0.0,k=0;k<n;k++){
    scanf("%lf%lf",&w,&v);
    a[k].weight = w;a[k].value=v;totvalue += v;
}
printf("输入限制重量：\n");scanf("%lf",&limitweight);
//for (k=0;k<n;k++)
//printf("w=%lfv=%lf",&a[k].weight,&a[k].value);
maxvalue = 0.0;
for (k=0;k<n;k++)
	find(0,0.0,totvalue);
for (k=0;k<n;k++)
	if(option[k]) printf("%4d",k+1);
printf("\n总价值为%.2f\n",maxvalue);
}