贪心算法-蒲公英云

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。举一个简单的贪心法例子，平时购物找钱时，为使找回的零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑各币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种，这就是在采用贪心法。需要注意的是，贪心法并不总能得到最优解。

贪心法求得最优解的问题中一般具有两个重要的性质：

（1）最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题具有最优子结构是该问题可以采用动态规划法或贪心法求解的关键性质。

（2）贪心选择性质：指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。

以部分背包问题为例：

假设物品个数n=5,背包容量W=100，物品的基本信息如下图：

20171028173844502

为了得到最优解，必须把背包装满，现在用贪心策略求解，首先要选出度量的标准。

假设按照最大单位重量价值先放背包的原则。

C#代码实现如下：

private void btnOK_Click(object sender, EventArgs e)
        {
            int i;
            int n = 5;  //物品数量
            //已经按照单位重量价值进行排序：
            double []weight={30,10,20,50,40};
            double []v={65,20,30,60,40};
            double  W=100;
            double [] x = new double [5];
            for (i = 0; i < n; i++)
            {
                if (weight[i] <= W)   //如果背包剩余容量可以装下该物品
                {
                    x[i] = 1;
                    W = W - weight[i];
                }
                else
                {                   
                    break;
                }
            }
            if (i < n)   //如果还有物品可以部分装入背包中
            {
                x[i] = W / weight[i];
            }
            double sum = 0;  //最大价值
            for (i = 0; i < n; i++)
            {
                textBox1.Text = textBox1.Text +"      "+x[i].ToString();
                sum = sum + x[i] * v[i];
            }
            textBox2.Text = sum.ToString();
        }