算法进阶之贪心算法

迷南。 2022-06-08 11:15 256阅读 0赞

看着大家都在对自己学习过的算法进行总结，我也记录一下吧！

从贪心算法开始！

【前言】

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学就知道怎么贪。有人说贪心算法是最复杂的算法，原因也很简单：这世上会贪的人太多了，那轮到你我的份？

贪心算法思想

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择

只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有

问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况

下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本要素

贪心选择性质（最优子结构）。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，

即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

贪心算法的基本思路

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再

继续前进时，算法停止。  
  
  
实现该算法的过程

从问题的某一初始解出发；当 能满足条件时求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；

福利送上！

namespace 贪心算法 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void button1_Click(object sender, EventArgs e) { int n=5; double [] Values = new double [5] { 65, 20, 30, 60, 40 }; //物品价值 double [] Weights=new double [5] {30,10,20,50,40}; //物品重量 double W = 100; //背包载重为100 int i; double[] x = new double [5] ; for (i = 0; i < n; i++) { if ( Weights [i] <=W) { /* 如果背包剩余容量可以放下该物品*/ x [i]=1; W=W-Weights [i]; } else { //如果有物品可以部分放进背包内 x[i] = W / Weights[i]; break; //跳出for循环 } } double sum = 0; //求物品的最大价值 for (i = 0; i < n; i++) { textBox1.Text = textBox1.Text + " " + x[i].ToString(); //textBox2.Text = textBox2.Text + " " +( x[i] * Values[i]).ToString(); sum = sum + (x[i] * Values[i]); } textBox2.Text = sum.ToString(); } } }