概述

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

个人对贪心算法的理解是：贪心是有条件的，我们也常说贪心策略选择，具有一定的时效性。而通常，基于选择的性质，往往贪心算法会做一个排序。

性质

最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。

贪心选择
贪心选择是指所求问题的整体最优解，可以通过一系列局部最优的选择；例如背包问题中，我们放物品可以选择按物品价值最大的先放；可以选择按重量最小的物品来放；我们可以选择单位重量的价值最大来访。。。我们从局部最优解，扩展到整体最优解。

解题步骤

1. 数学模型

2. 分解成子问题

3. 局部最优

4. 局部最优到整体最优

贪心VS动态规划

这种算法很相似，传送门：，于是将他们比较了一下，同时借助了一下思维导图，如下（大家拍砖斧正）：

C# Demo

自己顺了一遍之后，用C#实现了一下贪心算法，路过的小伙伴多提建议，其中进行简单排序的地方，用了一下堆排序，顺便温习一下堆排序时间复杂度：O (nlgn)。我们一起学习，共同进步~

#region 实体goods--刘雅雯--2017年9月23日16:46:58    ///     /// 物品类用于存储物品的属性    /// 
    public class Goods{        //编号        public int flag;        //重量        public int weight;        //价值        public int value;        //单位重量        public double vw;        ///         /// goods的构造函数        /// 
        /// 编号        /// 重量        /// 价值        /// 单位重量价值        public Goods(int flag, int weight, int value, double vw)        {            this.flag = flag;            this.weight = weight;            this.value = value;            this.vw = vw;        }    }#endregion

#region 堆排序进行筛选--刘雅雯--2017年9月23日16:45:21        ///         /// 排序算法--将单位重量的价值，降序排列,利用堆排序        /// 
        /// 物品集        /// 
   
    单位重量价值，降序的物品集
           public Goods[] Sort(Goods[] goods ) {            for (int i = goods.Length/2; i >=1; i--)            {                //筛选：使得二叉树结构中，每一个父节点，都比孩子节点小                sift(goods, i, goods.Length);            }            for (int j = goods.Length; j>=1; j--)            {                //交换两个元素，第一个位置，已是最小的元素                Goods[] temp = new Goods[1];                temp[0] = goods[0];  //取出第一个位置的元素存起来                goods[0]= goods[j-1]; //第一个位置，放最后一个元素                goods[j - 1] = temp[0]; //最后一个位置，放入第一个元素对象                sift(goods, 1, j-1);  //进行一次筛选，使得第一个位置的数最小            }            return goods;        }       ///         /// 堆排序的筛选过程       /// 
       /// 数组       /// 第i位置（放较小的数）       /// 数组的个数        public void sift(Goods[] goods, int k,int n) {            int i = k;            int j = 2 * i;            Goods[] tempGoods = new Goods[1];            tempGoods[0]= goods[k - 1];            if (j<=n)            {                if (j
   
     goods[j+1-1].vw) //比较子孩子们                {                    j++;                }                if (goods[k-1].vw > goods[j-1].vw) //比较父节点和较小的一个孩子                {                    goods[i-1] = goods[j-1]; //在第i个位置放入j个位置放的对象                    i = j;               //子节点变为父节点，递归的意思                     j = 2 * i;                }            }            goods[i-1] = tempGoods[0];//之前存起来的数，找到了她的位置        }         }        #endregion

#region 贪心算法背包问题--刘雅雯--2017年9月23日16:46:10        ///         /// 贪心算法        /// 
        /// 背包的总容量        /// 物品        /// 
           public float[] GreedyKnapsack(int W,Goods[] goods ) {            //状态，0表示不在，1表示在，0-1表示部分在            float[] state = new float[5];            int i;            //初始化状态            for ( i = 1; i <= goods.Length; i++)            {                state[i - 1] = 0;            }            for ( i = 1; i <= goods.Length; i++)            {                if (goods[i-1].weight<=W) //当整个物品可以放下时                {                    state[i - 1] = 1;                    value = value + goods[i - 1].value;                    W = W - goods[i - 1].weight;                }                else                {                    break;   //当整个物品放不进去，直接跳出整个循环，后面的不再判断                }            }            //只有部分物品可以放进去            if (i<=goods.Length)            {                state[i - 1] = W/(float)goods[i - 1].weight;                value = value + goods[i - 1].value * state[i - 1];            }            return state;        }        #endregion

private void Greedy_Click(object sender, EventArgs e)        {                      Goods[] goods = new Goods[5] {
  new Goods(1,30,65,2.1),new Goods(2,50,60,1.2),new Goods(3,40,40,1) ,new Goods(4,20,30,1.5), new Goods(5,10,20,2)};            Goods[] newGoods = new Goods[5];            float[] state = new float[5];            //得到goods按照单位重量价值降序排列的newGoods            newGoods = Sort(goods);            state= GreedyKnapsack(100, goods);            for (int i = 1; i <= state.Length; i++)            {                label2.Text = label2.Text + state[i - 1].ToString() + "， ";            }            label2.Text = label2.Text + "\r\n" + "背包的总价值为：" + value;        }

运行的结果如下，页面有些丑，这次的侧重点在逻辑上，望见谅~

感受

算法，很大的程度上锻炼自己的逻辑思考，最近研究算法这方面的感受深刻，严谨的小伙伴，在算法的路上不断精进。

你可能感兴趣的文章