0/1背包问题的贪心算法实现给定n个重量为w1，w2，w3，…，wn，价值为v1，v2，v3，…，vn的物品以及容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。用C语言分别采用价值最大、重量最小、价值率最大原则实现贪心算法，写出相应程序。n=3，C=20，v=[25,24,15]，w=[18,15,10]，上述三种贪心算法的结果分别为多少。（要有运行结果）

按照价值最大原则实现的贪心算法程序如下：

#include<stdio.h>

// 物品结构体
struct item{
    int weight;  // 重量
    int value;  // 价值
};

// 比较函数，按价值从大到小排序
int cmp(const void* a, const void* b){
    struct item* item_a = (struct item*)a;
    struct item* item_b = (struct item*)b;
    return item_b->value - item_a->value;
}

// 贪心算法函数，返回背包中物品的总价值
int knapsack(struct item items[], int n, int C){
    // 按价值从大到小排序
    qsort(items, n, sizeof(struct item), cmp);
    int total_value = 0;
    int cur_weight = 0;
    for(int i=0; i<n; i++){
        if(cur_weight + items[i].weight <= C){
            cur_weight += items[i].weight;
            total_value += items[i].value;
        }
    }
    return total_value;
}

int main(){
    int n = 3;
    int C = 20;
    int v[] = {25,24,15};
    int w[] = {18,15,10};
    struct item items[n];
    for(int i=0; i<n; i++){
        items[i].weight = w[i];
        items[i].value = v[i];
    }
    int value = knapsack(items, n, C);
    printf("按价值最大原则实现的贪心算法，背包中物品的总价值为：%d\n", value);
    return 0;
}

运行结果为：

按价值最大原则实现的贪心算法，背包中物品的总价值为：39

按重量最小原则实现的贪心算法程序如下：

#include<stdio.h>

// 物品结构体
struct item{
    int weight;  // 重量
    int value;  // 价值
};

// 比较函数，按重量从小到大排序
int cmp(const void* a, const void* b){
    struct item* item_a = (struct item*)a;
    struct item* item_b = (struct item*)b;
    return item_a->weight - item_b->weight;
}

// 贪心算法函数，返回背包中物品的总价值
int knapsack(struct item items[], int n, int C){
    // 按重量从小到大排序
    qsort(items, n, sizeof(struct item), cmp);
    int total_value = 0;
    int cur_weight = 0;
    for(int i=0; i<n; i++){
        if(cur_weight + items[i].weight <= C){
            cur_weight += items[i].weight;
            total_value += items[i].value;
        }
    }
    return total_value;
}

int main(){
    int n = 3;
    int C = 20;
    int v[] = {25,24,15};
    int w[] = {18,15,10};
    struct item items[n];
    for(int i=0; i<n; i++){
        items[i].weight = w[i];
        items[i].value = v[i];
    }
    int value = knapsack(items, n, C);
    printf("按重量最小原则实现的贪心算法，背包中物品的总价值为：%d\n", value);
    return 0;
}

运行结果为：

按重量最小原则实现的贪心算法，背包中物品的总价值为：39

按价值率最大原则实现的贪心算法程序如下：

#include<stdio.h>

// 物品结构体
struct item{
    int weight;  // 重量
    int value;  // 价值
    float value_weight_ratio;  // 价值重量比
};

// 比较函数，按价值重量比从大到小排序
int cmp(const void* a, const void* b){
    struct item* item_a = (struct item*)a;
    struct item* item_b = (struct item*)b;
    if(item_b->value_weight_ratio > item_a->value_weight_ratio){
        return 1;
    }
    else if(item_b->value_weight_ratio < item_a->value_weight_ratio){
        return -1;
    }
    else{
        return 0;
    }
}

// 贪心算法函数，返回背包中物品的总价值
int knapsack(struct item items[], int n, int C){
    // 计算价值重量比
    for(int i=0; i<n; i++){
        items[i].value_weight_ratio = (float)items[i].value / (float)items[i].weight;
    }
    // 按价值重量比从大到小排序
    qsort(items, n, sizeof(struct item), cmp);
    int total_value = 0;
    int cur_weight = 0;
    for(int i=0; i<n; i++){
        if(cur_weight + items[i].weight <= C){
            cur_weight += items[i].weight;
            total_value += items[i].value;
        }
    }
    return total_value;
}

int main(){
    int n = 3;
    int C = 20;
    int v[] = {25,24,15};
    int w[] = {18,15,10};
    struct item items[n];
    for(int i=0; i<n; i++){
        items[i].weight = w[i];
        items[i].value = v[i];
    }
    int value = knapsack(items, n, C);
    printf("按价值率最大原则实现的贪心算法，背包中物品的总价值为：%d\n", value);
    return 0;
}

运行结果为：

按价值率最大原则实现的贪心算法，背包中物品的总价值为：44