4.物品可以分割的背包(Fractional Knapsack)問題 Solution

貪婪準則是先計算所有物品的單位重量的價值，將所有物品以單位重量的價值由大到小進行排序，取最大的單位重量的價值物品開始，若可以放進背包就放入背包，一直到最後放不下為止或所有物品都已經放入，最後放不下的部分取剩餘未放入物品的最高單位重量的價值物品，取其中一部分到背包重量的上限為止，到此求得背包的負重能力範圍內的放入背包所有物品的最大價值。

#include<iostream>
#include<algorithm>
using namespace std;
struct Obj{
  int w; //weight 重量
  int v; //value  價值
  double vw;
};

//CP值最高的放前面
bool cmp(Obj a,Obj b){
  return (a.vw>b.vw);
}
int main(){

  int n,k,tempK;
  double totalValue;//總價值，也就是答案
  Obj obj[101];

  while(cin>>n){

    //輸入每個物品的重量與價值，計算出這個物品的CP值
    for(int i=0;i<n;i++){
      cin >> obj[i].w >> obj[i].v;
      obj[i].vw=(double)obj[i].v/obj[i].w; //價值÷重量=CP值
    }

    cin >> k; //k代表背包負重
    tempK=k;  //暫存負重

    sort(obj,obj+n,cmp);//CP值最高的放前面

    for(int i=0;i<n;i++){
      if (obj[i].w<=tempK) {//如果還沒超重，把物品放進包包
        totalValue+=obj[i].v;
        tempK-=obj[i].w;     //背包容量變少
      }else{
        //目前的物品無法直接放進包包
        //計算如果將物品切下來放進包包
        totalValue+=(double)obj[i].vw*tempK;
        break;
      }
    }
    cout << totalValue << endl;

  }
}