分数背包问题贪心算法

分数背包问题是指一个背包有一定的容量，可以装入一些物品，每种物品有重量和价值两个属性。要求在不超过背包容量的前提下，选择一些物品装入背包，使得背包中物品的总价值最大。

贪心算法思路如下：

1. 计算每种物品的单位价值（即每一单位重量所对应的价值）。

2. 按照单位价值从大到小的顺序对物品进行排序。

3. 依次选择单位价值最高的物品放入背包中，直到背包装满或者物品都被选择完为止。

代码实现如下：

#include <iostream>
#include <algorithm>
using namespace std;

struct Item {
    int weight; // 物品重量
    int value; // 物品价值
    double unitValue; // 单位价值
};

bool cmp(Item a, Item b) {
    return a.unitValue > b.unitValue;
}

double fractionalKnapsack(int W, Item arr[], int n) {
    // 计算每个物品的单位价值
    for (int i = 0; i < n; i++) {
        arr[i].unitValue = (double)arr[i].value / arr[i].weight;
    }

    // 按照单位价值从大到小排序
    sort(arr, arr + n, cmp);

    double totalValue = 0; // 背包中物品的总价值
    int weightLeft = W; // 剩余的背包容量

    for (int i = 0; i < n; i++) {
        if (weightLeft == 0) { // 背包已经装满
            break;
        }
        if (arr[i].weight <= weightLeft) { // 当前物品可以完整地装入背包中
            totalValue += arr[i].value;
            weightLeft -= arr[i].weight;
        } else { // 当前物品只能部分地装入背包中
            totalValue += arr[i].unitValue * weightLeft;
            weightLeft = 0;
        }
    }

    return totalValue;
}

int main() {
    int W = 50; // 背包容量
    Item arr[] = {{10, 60, 0}, {20, 100, 0}, {30, 120, 0}}; // 物品重量、价值和单位价值
    int n = sizeof(arr) / sizeof(arr[0]);

    double maxValue = fractionalKnapsack(W, arr, n);
    cout << "背包能装入的最大价值为：" << maxValue << endl;

    return 0;
}