用不同贪心策略解决0-1背包问题c语言

好的，我可以为您讲解用不同贪心策略解决0-1背包问题的思路。

0-1背包问题是指有一组物品，每个物品有一个重量和一个价值，在限定的总重量内，选择一些物品装入背包，使得背包中物品的总价值最大。这个问题可以用贪心算法来解决。

下面是两种不同的贪心策略：

1. 按照单位重量价值最大的顺序选择物品。
这种策略称为价值主导策略。具体实现时，可以将物品按照单位重量价值从大到小排序，然后依次选择单位重量价值最大的物品放入背包中，直到放满为止。

2. 按照单位重量重量最小的顺序选择物品。
这种策略称为重量主导策略。具体实现时，可以将物品按照重量从小到大排序，然后依次选择重量最小的物品放入背包中，直到放满为止。

下面是C语言代码实现：

#include <stdio.h>
#include <stdlib.h>

struct item {
    int weight;
    int value;
};

int cmp(const void *a, const void *b) {
    const struct item *ia = (const struct item *)a;
    const struct item *ib = (const struct item *)b;
    double ra = (double)ia->value / ia->weight;
    double rb = (double)ib->value / ib->weight;
    return (ra < rb) ? 1 : -1;
}

int knapsack(struct item *items, int n, int capacity, int strategy) {
    int i, j;
    int result = 0;
    qsort(items, n, sizeof(struct item), cmp);
    if (strategy == 1) { // 价值主导策略
        for (i = 0; i < n && capacity > 0; i++) {
            if (items[i].weight <= capacity) {
                result += items[i].value;
                capacity -= items[i].weight;
            }
        }
    } else if (strategy == 2) { // 重量主导策略
        for (i = 0; i < n && capacity > 0; i++) {
            if (items[i].weight <= capacity) {
                result += items[i].value;
                capacity -= items[i].weight;
            }
        }
    }
    return result;
}

int main() {
    struct item items[] = {{2, 10}, {3, 5}, {5, 15}, {7, 7}, {1, 6}, {4, 18}, {1, 3}};
    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 15;
    int result1 = knapsack(items, n, capacity, 1);
    int result2 = knapsack(items, n, capacity, 2);
    printf("总价值（价值主导策略）：%d\n", result1);
    printf("总价值（重量主导策略）：%d\n", result2);
    return 0;
}

上面的代码中，`cmp`函数是用来比较两个物品的大小，根据单位重量价值从大到小排序。`knapsack`函数是用来求解0-1背包问题的，根据不同的策略选择物品并计算总价值。在`main`函数中，我们构造了一组物品，然后分别使用价值主导策略和重量主导策略求解，最后输出结果。

希望我的解答能够帮到您！