贪心算法求解背包问题C语言代码

以下是贪心算法求解背包问题的C语言代码：

#include <stdio.h>

void greedy_knapsack(int n, float w[], float p[], float c) {
    int x[n], i;
    float weight = 0.0, profit = 0.0;
    for (i = 0; i < n; i++)
        x[i] = 0;
    while (weight < c) {
        int best_item = -1;
        float best_ratio = -1.0;
        for (i = 0; i < n; i++) {
            if (x[i] == 0) {
                float ratio = p[i] / w[i];
                if (ratio > best_ratio) {
                    best_ratio = ratio;
                    best_item = i;
                }
            }
        }
        if (best_item == -1)
            break;
        x[best_item] = 1;
        weight += w[best_item];
        profit += p[best_item];
    }
    printf("Selected items:\n");
    for (i = 0; i < n; i++) {
        if (x[i])
            printf("  item %d (weight=%.2f, profit=%.2f)\n", i + 1, w[i], p[i]);
    }
    printf("Total weight: %.2f\n", weight);
    printf("Total profit: %.2f\n", profit);
}

int main() {
    int n, i;
    float w[100], p[100], c;
    printf("Enter the number of items: ");
    scanf("%d", &n);
    printf("Enter the weights and profits of each item:\n");
    for (i = 0; i < n; i++) {
        printf("  item %d: ", i + 1);
        scanf("%f %f", &w[i], &p[i]);
    }
    printf("Enter the capacity of the knapsack: ");
    scanf("%f", &c);
    greedy_knapsack(n, w, p, c);
    return 0;
}

该算法基于价值密度最高的原则，每次选择具有最高价值密度的物品放入背包中。由于它只考虑了当前物品的价值，而没有考虑将来可能选择的物品，因此可能会导致最终选择的解不是最优解。