0/1背包问题的贪心算法实现 给定n个重量为w1，w2，w3,...，wn，价值为v1，v2，v3,...，vn的物品以及容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。(1)分别采用价值最大、重量最小、价值率最大原则实现贪心算法，写出完整代码

1. 价值最大原则的贪心算法实现：

#include <iostream>
#include <algorithm>

using namespace std;

struct Item{
    int weight;
    int value;
};

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

double fractional_knapsack(int capacity, Item arr[], int n){
    double total_value = 0.0;
    sort(arr, arr+n, cmp);

    for(int i=0; i<n; i++){
        if(arr[i].weight <= capacity){
            capacity -= arr[i].weight;
            total_value += arr[i].value;
        }
        else{
            total_value += arr[i].value * ((double)capacity / arr[i].weight);
            break;
        }
    }
    return total_value;
}

int main(){
    int capacity = 50;
    Item arr[] = {{20, 100}, {10, 60}, {40, 120}, {30, 90}};
    int n = sizeof(arr) / sizeof(arr[0]);

    double result = fractional_knapsack(capacity, arr, n);
    cout << "Maximum value we can obtain = " << result << endl;
    return 0;
}

2. 重量最小原则的贪心算法实现：

#include <iostream>
#include <algorithm>

using namespace std;

struct Item{
    int weight;
    int value;
};

bool cmp(Item a, Item b){
    return a.weight < b.weight;
}

int knapsack(int capacity, Item arr[], int n){
    int total_value = 0;
    sort(arr, arr+n, cmp);

    for(int i=0; i<n; i++){
        if(arr[i].weight <= capacity){
            capacity -= arr[i].weight;
            total_value += arr[i].value;
        }
    }
    return total_value;
}

int main(){
    int capacity = 50;
    Item arr[] = {{20, 100}, {10, 60}, {40, 120}, {30, 90}};
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = knapsack(capacity, arr, n);
    cout << "Maximum value we can obtain = " << result << endl;
    return 0;
}

3. 价值率最大原则的贪心算法实现：

#include <iostream>
#include <algorithm>

using namespace std;

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

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

double fractional_knapsack(int capacity, Item arr[], int n){
    double total_value = 0.0;

    for(int i=0; i<n; i++){
        arr[i].ratio = (double)arr[i].value / arr[i].weight;
    }
    sort(arr, arr+n, cmp);

    for(int i=0; i<n; i++){
        if(arr[i].weight <= capacity){
            capacity -= arr[i].weight;
            total_value += arr[i].value;
        }
        else{
            total_value += arr[i].value * ((double)capacity / arr[i].weight);
            break;
        }
    }
    return total_value;
}

int main(){
    int capacity = 50;
    Item arr[] = {{20, 100}, {10, 60}, {40, 120}, {30, 90}};
    int n = sizeof(arr) / sizeof(arr[0]);

    double result = fractional_knapsack(capacity, arr, n);
    cout << "Maximum value we can obtain = " << result << endl;
    return 0;
}