贪心算法-部分背包问题

什么是贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

问题描述

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci，得到的价值是 Wi，物品可以分割。求解将哪些物品装入背包可使价值总和最大。

解题思路

贪心算法追求局部最优，那么在部分背包问题中，我们要追求最大收益就要先装价值最高的商品，再装剩下商品中价值最高的，直至装满或没有能装的商品。

代码实现

void Knapsack(int n, float M, float v[], float w[], float x[])
{
    Sort(n, v, w);
    int i;
    for (i = 1; i <= n; i++)
        x[i] = 0;
    float c = M;
    for (i = 1; i <= n; i++)
    {
        if (w[i] > c)
            break;
        x[i] = 1;
        c -= w[i];
    }

    if (i <= n)
        x[i] = c / w[i];
}