0-1背包递归程序终稿.cpp

在0和1情况下进行背包问题解决

#include <stdio.h>
#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了
int n;//物品总种数
double limitW;//限制的总重量
double totV;//全部物品的总价值
double maxv;//解的总价值
int option[N];//解的选择

int k;
int cop[N];//当前解的选择
struct {//物品结构
double weight;
double value;
}a[N];

 double w,v;
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值
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 add()
{printf("输入物品种数:");
   scanf("%d",&n);
 printf("输入限制重量:");
 scanf("%lf",&limitW);}
void  com( )
{  
  printf("输入各物品对应的重量和价值:");
  for(totV=0.0,k=0;k<n;++k){
   scanf("%lf %lf",&w,&v);
  a[k].weight = w;a[k].value = v;
  totV += v;
  }
 
 return;
}

void result()
{
com();
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("选择物体编号：%2d  ",k+1);
printf("\n总价值为: %2f",maxv);
}


void main()
{  int choice;
  
 loop:
  while(1)
  {
  printf("关于0-1背包程序菜单如下：\n\n");
  printf("     1.输入初始数据:\n");
  printf("     2.具体数值，计算并输出\n");
  printf("     3退出\n\n");
  printf("请选择功能：\n");
  scanf("%d",&choice);
  if(choice!=1&&choice!=2&&choice!=3&&choice!=4)
  {printf("您输入有误！请重新输入选择：\n");goto loop;}

  else if (choice==1){add();printf("\n");goto loop;}
  else if(choice==2){result();printf("\n\n");goto loop;}
  else if(choice==3) return;
  }


}