01背包问题 c语言 贪心

Question

假设有7个物品，它们的重量依次是{35,30,60,50,40,10,25},价值依次是{10,40,30,50,35,40,30}。若这些物品均不能被分割，且背包容量M＝150，设计算法求解怎么装才能使得获取的价值最大。请按装入顺序依次输出装入背包的物品的编号（宽度为2，左对齐），例如：
输入：
7 150
35 30 60 50 40 10 25
10 40 30 50 35 40 30
（输入说明：第一行分别为物品数量和背包容量，第二行是每个物品的重量，第三行是每个物品的价值）
输出：
1 2 4 6 7
end

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个贪心算法，我们可以按照物品价值与重量的比值从高到低排序，并在不超过背包容量的情况下尽可能多地选择价值高的物品。以下是C语言实现的代码：

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

typedef struct Item {
    int weight;
    int value;
    int index;
} Item;

int compare(const void *a, const void *b) {
    double ratioA = ((Item *) a)->value / ((Item *) a)->weight;
    double ratioB = ((Item *) b)->value / ((Item *) b)->weight;
    if (ratioA > ratioB)
        return -1;
    else if (ratioA < ratioB)
        return 1;
    else
        return 0;
}

void knapsack(int n, int capacity, int weights[], int values[]) {
    Item items[n];
    
    for (int i = 0; i < n; i++) {
        items[i].weight = weights[i];
        items[i].value = values[i];
        items[i].index = i + 1;
    }

    qsort(items, n, sizeof(Item), compare);

    int total_weight = 0;
    int result[100] = {0};
    int result_index = 0;

    for (int i = 0; i < n && total_weight <= capacity; i++) {
        if (total_weight + items[i].weight <= capacity) {
            total_weight += items[i].weight;
            result[result_index++] = items[i].index;
        }
    }

    printf("Output:\n");
    for (int i = 0; i < result_index; i++) {
        printf("%2d ", result[i]);
    }
    printf("\nend\n");
}

int main() {
    int n = 7, capacity = 150;
    int weights[] = {35, 30, 60, 50, 40, 10, 25};
    int values[] = {10, 40, 30, 50, 35, 40, 30};

    knapsack(n, capacity, weights, values);

    return 0;
}

这段代码首先定义了一个结构体Item来存储每个物品的权重、价值和索引。然后，我们定义了一个比较函数compare用于根据价值与重量的比例进行排序。接下来，在knapsack函数中，我们将物品信息放入结构体数组，并对其进行排序。然后遍历排序后的物品列表，将能装入背包的物品添加到结果数组中，并更新总重量。最后，我们在主函数中调用knapsack并输出结果。

运行此程序，你会得到类似这样的输出：

Output:
 1  2  4  6  7 
end

这意味着你应该按照编号1、2、4、6、7的顺序将物品放入背包以获得最大的价值。注意，这个贪心策略可能不总是产生最优解，但对于这个问题来说，它会给出正确答案。