贪心算法案例、np完全问题及java代码实现

贪心算法（greedyalgorithm）是指在解决问题时，每一步都采用最好的或最优的选项（即最有利的），所以是可取的。如果结果是最好或最优的算法。

贪心算法得到的结果往往不是最优结果（有时是最优解），而是相对（接近）最优解。

• 贪心算法没有固定的算法求解框架。该算法的关键是贪心策略的选择。根据不同的问题选择不同的策略。
• 需要注意的是，策略的选择必须没有副作用，即特定国家的选择不会影响之前的情况，而只与当前的情况有关。因此，所采用的贪心策略必须仔细分析，看其是否令人满意且没有后遗症。

比如最短路径问题（第一广度，狄克斯特拉），前面介绍的就是贪心算法，但是在问题策略的选择上，是可以得到最优解的。

基本思路

解决问题的基本思路是：

1.创建一个数学模型来描述问题

2。将要解决的问题分成几个子问题

3。对每个子问题求解，得到子问题

4的局部最优解。将子问题对应的局部最优解组合成所有原问题的近似最优解

假设下面有一门课程，我们希望在一个班级中管理多门课程：

这个问题看似需要花很多心思，但算法其实很简单：

1。选择结束最早的班是本班第一个上课的班。 2、接下来选择第一节课结束后开始的课，最早结束该课。这将是该班的二年级。

重复此操作即可找到答案。这里的选择策略是排序先结束且与上一课不冲突的课程。因为每次都是最早选择最后一个，所以后面的就没有时间了。您拥有的越多，您可以安排的课程就越多。

每节课的选择都是该策略的局部最优解（直到最长时间），所以最终的结果也是近似最优解（本例中就是最优解）。（本案例的代码实现是一个简单的时间对比过程）

案例2

背包问题：有一个容量为35公斤的背包。提供以下物品：

所需目标是最大化总价值包装好背包，并且不要超过重量。

很容易数，所以只有3项，但实际情况可能有数千项。

与上面使用贪心算法相同。由于总值必须是最大值，因此每次加载最贵的，然后加载下一个最贵的。选择结果如下：

选择：音箱+笔，总价值3000+200=3200

不是最优方案：吉他+笔记本电脑，总价值1500+2000=3500♿策略选择课程有时不太固定，可以如下：

（1）每次选择数值最高的一项，最终权重不超过：

选择：音箱+笔，总值3000+200=3200

(2)每次选择重量最大的，不超过最终重量（有可能只有需要最大重量的才会优先）：

选择：音箱+笔，合计值3000 + 200 = 3200

(3) 每次选择数值最大的单位（价格/重量），最终重量不超过：

选择：笔+显示器，总值200 + 2999 = 3199

上面的最终结果并不是最优解。在这种情况下，贪心算法无法得到最优解，只能得到一个近似的最优解，也可以认为是该算法的局限性之一。如果需要得到此类问题的最优解，可以使用动态规划算法（以后更新也可以关注密码公众号，第一时间获取更新信息）。 ？如何选择最少的广播电台，让所有区域都能收到信号。

如何找到一组覆盖所有地区的广播电台？听起来很简单，但是却实现了。非常复杂，使用完整方法实现：

(1) 列出每个可能的广播电台的集合，称为功率集。假设总共有n个广播电台，总共有2ⁿ广播电台组合

(2) 在这些集合中，选择覆盖整个区域的最小集合，假设n不存在，但当n太时较大，假设每秒可以计算 10 个子集

A->B->C
A->C->B
B->A->C
B->C->A
C->A->B
C->B->A
复制代码