c语言贪心算法算法设计背包问题

背包问题是一个经典的动态规划问题，但是也可以使用贪心算法来解决。以下是使用贪心算法来解决背包问题的步骤：

1. 首先计算每个物品的单位价值（即价值除以重量），并将物品按照单位价值从大到小排序。
2. 从单位价值最高的物品开始，尽可能多地将该物品加入背包中，直到背包无法容纳更多的物品为止。
3. 重复步骤2，直到所有物品都被考虑过。

下面是使用C语言实现贪心算法解决背包问题的示例代码：

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

#define N 100

typedef struct {
    int weight;
    int value;
    double unit_price;
} Item;

void sort_items(Item *items, int n);
int knapsack(Item *items, int n, int capacity);

int main() {
    Item items[N];
    int n, capacity, i;

    printf("Enter the number of items: ");
    scanf("%d", &n);

    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &capacity);

    printf("Enter the weight and value of each item:\n");
    for (i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].value);
        items[i].unit_price = (double) items[i].value / items[i].weight;
    }

    sort_items(items, n);
    int max_value = knapsack(items, n, capacity);
    printf("The maximum value of items that can be put into the knapsack is %d.\n", max_value);

    return 0;
}

void sort_items(Item *items, int n) {
    int i, j;
    Item temp;

    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (items[j].unit_price < items[j+1].unit_price) {
                temp = items[j];
                items[j] = items[j+1];
                items[j+1] = temp;
            }
        }
    }
}

int knapsack(Item *items, int n, int capacity) {
    int i, total_weight = 0, total_value = 0;

    for (i = 0; i < n; i++) {
        if (total_weight + items[i].weight <= capacity) {
            total_weight += items[i].weight;
            total_value += items[i].value;
        } else {
            break;
        }
    }

    return total_value;
}

在这个示例中，我们使用一个结构体来表示每个物品，其中包含重量、价值和单位价值三个属性。`sort_items` 函数根据单位价值对物品进行排序，`knapsack` 函数使用贪心算法来选择物品并计算最大价值。