用贪心算法解决背包问题_背包问题贪心算法

背包问题分为两种，一种是一般背包问题，也称为背包问题（Knapsack Problem）背包问题可以选择物品的一部分装入，若装入第i件物品的一部分xi（0<=xi<=1）则该部分物品的重量为wixi，其获得收益为pixi；另一种是0/1背包问题，如果一件物品不能分割，只能作为整体或者装入，或者不装入，则称之为0/1背包问题。

背包问题：

已知一个载重量为M的背包和n件物品，第i件物品的重量为wi，如果将第i件物品全部装入背包，将有收益pi，这里wi>0，pi>0,0<i≤n-1。所谓背包问题，是指求一种最佳装载方案使得装入背包中物品的收益最大。

贪心算法究竟是什么呢？

贪心算法只是一种算法，它是基于贪心策略来编写的算法，贪心算法可以看作是贪心策略的具象化，算法是具体的，策略是模糊的。

贪心策略：

贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优解）的一种解题方法，也就是说贪心策略只是某种意义上的局部最优解。

贪心算法：贪心算法是通过分步决策，每步都形成局部解，利用这些局部解来构成问题的最终解。

贪心算法求解问题的过程通常包括三个步骤：

1.分解：将原问题分解为若干相互独立的阶段。

2.求解：对每个阶段求局部最优解，即进行贪心选择。

3.合并：将各个阶段的解合并为原问题的一个可行解

（这里主要讲解背包问题，仅简单介绍贪心算法，让大家能理解背包问题中的贪心算法。）

算法分析：

背包问题用Knapsack算法进行求解，Knapsack主要是计算各种物品价值的单位之比，也就是性价比，将用两个实例对背包问题中的贪心策略进行讲解。我们只需要按性价比来装入各种物品，即将局部最优解组合起来，就可以得到某种意义上的最优解。

实例一：

设有载重能力M=20的背包和3件物品0、1、2的重量为：（w0,w1,w2）=(18,15,10),物品装入背包的收益为：（p0，p1，p2）=（25，24，15）。

用贪心算法求解该背包问题按照算法 Knapsack，首先计算单位重量比 pi/wi;，得到(p0/wo;p1/w1,p2/w2)=(25/18,24/15,15/10)(1.39,1.6,1.5),并按照降序排列得到(p1/w1，p2/w2，p0/w0)= (25/18，24/15，15/10) =(1.6，1.5，1.39)选择使单位重量收益最大的物品装入背包，即按照单位重量比 pi/wi的非降次序选择物品。（在这段中第一串标红的数字就是3件物品的性价比，第二串标红的数字就是按照高低排序的性价比，我们在装入物品时，就按照排序后的性价比尽可能装入物品，才能使背包物品价值最大化。）

先选入1号物品，再选入2号物品，但由于背包的容量剩余20-15=5，因此2号物品装入1/2，0号物品不装入，这样得到的解为（x0，x1，x2）=（0，1，1/2），它的总收益为31.5，总收益最大。

实例二：

设有背包问题时实例n=7，m=15，（w0，w1，...，w6）=（2，3，5，7，1，4，1），物品装入背包的收益为：（p0，p1，...，p6）=（10，5，15，7，6，18，13）。用贪心算法求解这一实例的最优解和最大收益。

那么该价值和重量的比值应当=（5，1.6，3，1，6，4.5，13），再将这个性价比进行排序，得出排序后的结果为=（13，6，5，4.5，3，1.6，1），这个性价比排序他们的重量分别是（1，1，2，4，5，3，7）。根据性价比排序进行装入，他们前五个应该全部装入背包，最终占据13重量，第六个物品应当占据最后2重量，第七个物品应当不装入。但因代码问题，结果略有谬误，因使用整形而不是使用浮点型，所以第七个物品选择大小超出显示范围。

代码6，7选择错误，根据程序选择，第6件物品选6/10应当占据1.8重量，所以剩余0.2分配给第七件物品，但如果手动计算发现，同样为0.2重量的物品，第6件的价值约为0.33，第七件的价值约为0.28，所以代码在选择上有错误。

源代码：

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

typedef struct {
    float weight; 
    float value;  
} Item;

int compare(const void *a, const void *b) {
    Item *itemA = (Item *)a;
    Item *itemB = (Item *)b;
    float ratioA = itemA->value / itemA->weight;
    float ratioB = itemB->value / itemB->weight;
    return (ratioB > ratioA) - (ratioB < ratioA);
}

void Knapsack(int n, float capacity, Item items[], float x[], float *value) {
    *value = 0.0;
    qsort(items, n, sizeof(Item), compare);
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            x[i] = 1; 
            *value += items[i].value; 
            capacity -= items[i].weight; 
        } else {
            x[i] = capacity / items[i].weight; 
            *value += items[i].value * x[i]; 
            break; 
        }
    }
}

int main() {
    int n; 
    float capacity; 
    printf("请输入背包的容量: ");
    scanf("%f", &capacity);
    printf("请输入物品的数量: ");
    scanf("%d", &n);

    Item *items = (Item *)malloc(n * sizeof(Item));
    float *x = (float *)malloc(n * sizeof(float));

    for (int i = 0; i < n; i++) {
        printf("请输入物品 %d 的重量: ", i + 1);
        scanf("%f", &items[i].weight);
        printf("请输入物品 %d 的价值: ", i + 1);
        scanf("%f", &items[i].value);
    }

    float value;
    Knapsack(n, capacity, items, x, &value);

    printf("最大价值: %f\n", value);
    printf("物品选择: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", (int)(x[i] * 10)); 
    }
    printf("\n");

    free(items);
    free(x);

    return 0;
}