编辑代码

#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;
}