编辑代码

#include <iostream>
#include <stdio.h>
//#include <conio.h>
using namespace std;
int n = 4;//物品数量
double c = 13; //载重
double v[4]= {5,1,6,8}; //价值
double w[4] = {4,2,3,5};//重量
double cw = 0.0;//当前背包重量
double cp = 0.0;//当前背包中物品总价值
double bestp = 0.0;//当前最优价值
double perp[4];//单位物品价值(排序后)
int order[4] = {1,2,3,4};//物品编号
int put[4];//设置是否装入，为1的时候表示选择该组数据装入，为0的表示不选择该组数据
 
 
//按单位价值排序
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[]排序
            order[i]=order[j];
            order[j]=temporder;
 
            temp = v[i];//冒泡对v[]排序
            v[i]=v[j];
            v[j]=temp;
 
            temp=w[i];//冒泡对w[]排序
            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()
{
    knapsack();
    backtrack(1);
    printf("最优价值为：%lf\n",bestp);
    return 0;
}