背包问题贪心算法c语言

背包问题是一个经典的动态规划问题，贪心算法并不能得到最优解。但是可以使用贪心算法得到近似最优解。以下是背包问题的贪心算法C语言代码：

#include <stdio.h>

#define MAX 100 // 背包最大容量

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

// 按照单位价值从大到小排序
void sort(struct item items[], int n) {
    int i, j;
    struct item temp;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (items[i].value / items[i].weight < items[j].value / items[j].weight) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }
}

// 计算最大价值
int knapsack(struct item items[], int n, int capacity) {
    sort(items, n); // 按照单位价值从大到小排序
    int i, value = 0;
    for (i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            capacity -= items[i].weight;
            value += items[i].value;
        } else {
            value += items[i].value * capacity / items[i].weight;
            break;
        }
    }
    return value;
}

int main() {
    struct item items[] = {{10, 60}, {20, 100}, {30, 120}}; // 物品数组
    int n = sizeof(items) / sizeof(items[0]); // 物品个数
    int capacity = 50; // 背包容量
    int max_value = knapsack(items, n, capacity);
    printf("Maximum value: %d\n", max_value);
    return 0;
}

该算法首先按照单位价值从大到小排序，然后依次选择单位价值最大的物品放入背包中，直到背包无法再放下物品为止。如果当前物品不能完全放入背包中，则只放入一部分。