编辑代码

#include <iostream>
#include <stdio.h>
//#include <conio.h>
using namespace std;
int n;
double c;
double v[100];
double w[100];
double cw = 0.0;
double cp = 0.0;
double bestp = 0.0;
double perp[100];
int order[100];
int put[100];
void knapsack()
{
    int i,j;
    int temporder = 0;
    double temp = 0.0;
 for(i=1;i<=n;i++)
 perp[i]=v[i]/w[i]; 
for(i=1;i<=n-1;i++)
{
 for(j=i+1;j<=n;j++)
 if(perp[i]<perp[j])
 {
 temp = perp[i];  
 perp[i]=perp[j];
 perp[j]=temp;
  temporder=order[i];
 order[i]=order[j];
 order[j]=temporder;
 temp = v[i];
 v[i]=v[j];
 v[j]=temp;
 temp=w[i];
 w[i]=w[j];
 w[j]=temp; }
 }
}
 
void backtrack(int i)
{   
double bound(int i);
if(i>n) 
{
bestp = cp;
return;
}
   
if(cw+w[i]<=c)
{
  cw+=w[i];
  cp+=v[i];
 put[i]=1;
 backtrack(i+1);
 cw-=w[i];
 cp-=v[i];
    }
    if(bound(i+1)>bestp)
        backtrack(i+1);
}
double bound(int i)
{double leftw= c-cw;
double b = cp;
 while(i<=n && w[i]<=leftw)
{
 leftw-=w[i];
 b+=v[i];
i++;
}
if(i<=n)
 b+=v[i]/w[i]*leftw;
return b;
}

int main()
{
    int i;
    printf("请输入物品的数量和背包的容量：");
    scanf("%d %lf",&n,&c);
    printf("请依次输入%d个物品的重量:\n",n);
    for(i=1;i<=n;i++){
     scanf("%lf",&w[i]);
     order[i]=i;
    }
    printf("请依次输入%d个物品的价值:\n",n);
    for(i=1;i<=n;i++){
        scanf("%lf",&v[i]);
    }
    knapsack();
    backtrack(1);
    printf("最优价值为：%lf\n",bestp);
    printf("需要装入的物品编号是：");
    for(i=1;i<=n;i++)
    {
        if(put[i]==1)
            printf("%d ",order[i]);
    }
    return 0;
}