编辑代码

#include<stdio.h>
#define Max_n 20
int n=5;  //物品数量
int W=10;  //背包容量
int w[]={0,4,2,1,5,6};//物品重量
int v[]={0,5,3,2,3,5};//物品价值
int x[Max_n]; 
int maxv;  //最优结果
void HuisuBag(int i,int xw,int xv,int Sv[])//解空间树,xw:选择的总重量，xv选择的总价值，Sv：解向量
{
 if(i>n)   
 {
  if(xw==W&&xv>maxv)
  {
   maxv=xv;
   for(int j=0;j<=n;j++)
   x[j]=Sv[j];
   } 
  } 
  else  
  {
   Sv[i]=1; 
   HuisuBag(i+1,xw+w[i],xv+v[i],Sv);
   Sv[i]=0;
   HuisuBag(i+1,xw,xv,Sv); 
  }  
}
void Zuiyou() //最优结果
{
 printf("最大价值=%d，选择物品总重量=%d\n",W,maxv);
 printf("最优解(头个元素‘0’除外）：\n");
 int i; 
 for(i=1;i<=n;i++)
 if(x[i]==1)
 printf(" 选取第%d个物品\n",i);
 } 
 int main(){
  int Sv[Max_n];
  HuisuBag(1,0,0,Sv);
  Zuiyou();
  return 0;
 }