背包问题贪心选择算法c++代码

根据提供的引用内容，以下是背包问题贪心选择算法的C++代码：

void Knapsack(int n, float M, float v[], float w[], float x[]) {
    // 此函数可以直接使用已经排序好的v[]和w[]数组；
    // n为物品数；M为背包大小；v为物品价值数组；w为物品重量数组；x为占比数组；
    int i;
    float c;
    Sort(n, v, w);
    for(i=1; i<=n; i++) x[i] = 0; // 将每件物品装进去背包的部分与总体的占比置零，最大为1
    c = M;
    for(i=1; i<=n; i++){
        if(w[i]>c) break; // 若背包装不下，则跳出循环
        x[i] = 1;
        c -= w[i];
    }
    if(i<=n) x[i] = c/w[i]; // 若背包没有达到全部装进去的目的，则装入部分
}

相关问题

写出背包问题的贪心选择性质 自然语言描述背包问题贪心选择算法 C++语言描述背包问题贪心选择算法

贪心选择性质：对于背包问题中每个物品，计算其单位重量的价值（即价值/重量），然后按照单位重量价值从大到小排序。接着，依次选择单位重量价值最大的物品放入背包中，直至装满为止。

自然语言描述背包问题贪心选择算法：先将所有物品按照单位重量价值从大到小排序，然后从价值最高的物品开始依次放入背包中，直至不能再放为止。

C++语言描述背包问题贪心选择算法：

struct Item {
    int value;
    int weight;
    double unitValue;
};

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

double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr + n, cmp);
    int curWeight = 0;
    double finalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalValue += arr[i].value;
        } else {
            int remain = W - curWeight;
            finalValue += arr[i].unitValue * remain;
            break;
        }
    }

    return finalValue;
}

其中，`Item` 是物品结构体，包含价值、重量和单位重量价值三个属性；`cmp` 是重载的比较函数，用于按照单位重量价值从大到小排序；`fractionalKnapsack` 是背包问题的贪心选择算法函数，其中 `W` 是背包的容量，`arr` 是物品数组，`n` 是物品数量。在函数中，我们首先按照单位重量价值从大到小排序，然后依次选择单位重量价值最大的物品放入背包中，如果当前物品无法完全放入背包中，则按照比例放入，直至背包装满为止。最后返回放入背包中的物品总价值。

解决背包问题的贪心算法c++代码

背包问题有多种贪心算法，以下是其中一种可以解决 01 背包问题的贪心算法的 C++ 代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Item {
    int value;
    int weight;

    Item(int v, int w) : value(v), weight(w) {}
};

bool compare(Item a, Item b) {
    double ratio_a = (double)a.value / a.weight;
    double ratio_b = (double)b.value / b.weight;

    return ratio_a > ratio_b;
}

int knapsack(int capacity, vector<Item>& items) {
    sort(items.begin(), items.end(), compare);

    int current_weight = 0;
    int result = 0;

    for (int i = 0; i < items.size(); i++) {
        if (current_weight + items[i].weight <= capacity) {
            current_weight += items[i].weight;
            result += items[i].value;
        } else {
            int remaining_capacity = capacity - current_weight;
            result += items[i].value * ((double)remaining_capacity / items[i].weight);
            break;
        }
    }

    return result;
}

int main() {
    int capacity = 50;
    vector<Item> items = { {60, 10}, {100, 20}, {120, 30} };

    int max_value = knapsack(capacity, items);

    cout << "Maximum value: " << max_value << endl;

    return 0;
}

该算法的思路是先按照每个物品的价值和重量的比例从大到小排序，然后尽可能地选取价值重量比例最大的物品放入背包，直到背包满了为止。如果还有剩余的容量，就按照比例将剩余容量分配给下一个价值比例次高的物品。