Knapsack - Fractional 分数背包

http://www.geeksforgeeks.org/fractional-knapsack-problem/

An efficient solution is to use Greedy approach. The basic idea of greedy approach is to calculate the ratio value/weight for each item and sort the item on basis of this ratio. Then take the item with highest ratio and add them until we can’t add the next item as whole and at the end add the next item as much as we can. Which will always be optimal solution of this problem.

// Comparison function to sort Item according to val/weight ratio

bool cmp(struct Item a, struct Item b)

{

    double r1 = (double)a.value / a.weight;

    double r2 = (double)b.value / b.weight;

    return r1 > r2;

}

 

// Main greedy function to solve problem

double fractionalKnapsack(int W, struct Item arr[], int n)

{

    //    sorting Item on basis of ration

    sort(arr, arr + n, cmp);

 

    //    Uncomment to see new order of Items with their ratio

    /*

    for (int i = 0; i < n; i++)

    {

        cout << arr[i].value << "  " << arr[i].weight << " : "

             << ((double)arr[i].value / arr[i].weight) << endl;

    }

    */

 

    int curWeight = 0;  // Current weight in knapsack

    double finalvalue = 0.0; // Result (value in Knapsack)

 

    // Looping through all Items

    for (int i = 0; i < n; i++)

    {

        // If adding Item won't overflow, add it completely

        if (curWeight + arr[i].weight <= W)

        {

            curWeight += arr[i].weight;

            finalvalue += arr[i].value;

        }

 

        // If we can't add current Item, add fractional part of it

        else

        {

            int remain = W - curWeight;

            finalvalue += arr[i].value * ((double) remain / arr[i].weight);

            break;

        }

    }

 

    // Returning final value

    return finalvalue;

}

http://blog.csdn.net/wangjin123456789/article/details/40381727
在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O(nlogn)。为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

http://blog.csdn.net/yyc1023/article/details/41746771

1. double knapsack(vector<goods>  & vec,double v)  
2. {  
3.     //先将货物按照性价比排序  
4.     sort(vec.begin(),vec.end(),cmp);  
5.     //从性价比高的开始装入背包  
6.     double l = v;//背包的剩余容量  
7.     double sum = 0;//背包的总价值  
8.     for (int i = 0; i < vec.size(); i++)  
9.     {  
10.         if(l>0)  
11.         {  
12.             if(l>vec[i].weight)  
13.             {  
14.                 l -= vec[i].weight;  
15.                 vec[i].in = vec[i].weight;  
16.                 sum += vec[i].value;  
17.             }  
18.             else  
19.             {  
20.                 vec[i].in = vec[i].weight - l;  
21.                 sum += l*vec[i].ratio;  
22.                 l =0;  
23.                 break;  
24.             }  
25.               
26.         }  
27.     }  
28.     return sum;  
29. }