学步园

问题描述：给定一个在重量为M的背包，考虑n个物品，其中第i个物品的重量为weight(i),价值为value(i),要求把物品装满背包，且使背包内的物品价值最大。有两类背包问题,如果物品不可以分割，即要么装要么不装，成为0-1背包问题，如果物品可以分割，则称为背包问题。

knapsacks算法：先将物品按性价比从高到低排序，然后从性价比最高的物品开始选择，依次向后，当物品不能完全装满背包的时候，就只装一部分以装满背包。

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
struct bag{
    double weight;
    double value;
    double cost;     //性价比
};
bool cmp(const bag &a,const bag &b)
{
    return a.cost>=b.cost;
}
double knaspsack(int n,bag array[],double c);
int main()
{
    bag array[1000];
    double num1,num2;
    int i = 0,n=0;
    cin>>num1>>num2;
    while((num1!=0)||(num2!=0))
    {
        array[i].weight = num1;
        array[i].value = num2;
        array[i].cost = num1/num2;
        n=i;        //避免(0,0)影响结果
        i++;
        cin>>num1>>num2;
    }
    sort(array,array+n,cmp);//按性价比从高到低排序
    int capacity;           //背包容量
    cin>>capacity;
    cout<<knaspsack(n,array,capacity)<<endl;
    return 0;
}
double knaspsack(int n,bag array[],double c)
{
    double left = c;    //背包的剩余容量
    double b=0;
    int j=0;
    while(j<n&&array[j].weight<left)
    {
        left -= array[j].weight;
        b += array[j].value;
        j++;
    }
    if(j<n)     //装满背包剩余的空间
    {
        b+= 1.0*array[j].value*left/array[j].weight;
    }
    return b;
}

运行结果：

reference：《算法分析与设计》《算法设计与分析基础》