• 概述
• 解题思路
  • 选择价值最大的物品，放入背包。
  • 选择重量最轻的物品，放入背包。
  • 单位重量价值最大的物品，放入背包。
• 程序代码
  • 伪代码
  • Java代码
  • C++代码

概述

给定N个物品和一个容量为C的背包，物品i的重量是Wi，其价值为Vi，背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，但不能超过总容量。在背包问题中可以将物品的一部分装入背包（物品可以拆分的装入背包），但不能重复装入。

解题思路

用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直到背包装满。
至少有三种看似合适的贪心策略。

选择价值最大的物品，放入背包。

因为这可以尽可能快的增加背包的总价值，但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗的太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。

选择重量最轻的物品，放入背包。

因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗的慢了，但背包的价值却没能保证迅速的增长，从而不能保证目标函数达到最大。

单位重量价值最大的物品，放入背包。

最大价值和最大重量两种贪心策略或者只考虑背包价值的增长，或者只考虑背包容量的消耗，而为了求得背包问题的最优解，需要在背包价值增长和背包容量消耗二者之间寻找平衡。正确的贪心策略是选择单位重量价值最大的物品。
例如：有三个物品，其重量分别为{20,30,10}，价值分别为{60,120,50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如下图所示：

• 概述
• 解题思路
  • 有2种解题方法
    • 迭代方法
    • 递归方法
• 程序代码
  • 迭代方法
    • 伪代码
    • C++版本
    • Java版本
  • 递归方法

概述

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间$s_i$和一个结束时间$f_i$，且$s_i$<$f_i$。如果选择了活动i，则它在半开时间区间[$s_i$, $f_i$)内占用资源。若区间[$s_i$, $f_i$)与区间[$s_j$, $f_j$)不相交，则称活动i与活动j是相容的。也就是说，当$s_i$≥$f_j$或$s_j$≥$f_i$时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

解题思路

假定活动已按结束时间的单调递增顺序排序（小到大排序）：f1 ≤ f2 ≤ f3 ≤....≤ fn-1 ≤ fn
用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。
事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续i位置的下一个活动与集合A中活动比较相容性（集合A中的活动也就是上次比较的活动）。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置（迭代方法）。

有2种解题方法

迭代方法

每次总是选择具有最早完成时间的相容活动加入集合A中（默认第1个加入集合A中）。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间（因为添加到集合A中的时间最短，剩余的时间就长）。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
迭代方法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
若被检查的活动i的开始时间$s_i$小于最近选择的活动j的结束时间$f_i$，则不选择活动i，否则选择活动i加入集合A中。

迭代方法的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

• 引言
• 概念
• 基本思想
  • 重要特性
  • 存在问题
  • 最大特点
• 步骤

引言

平时购物找钱时，为了使找回零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就贪心算法。这种方法在这里总是最优的，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。
如果面值分别为1,5,11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应该找1个11单位的硬币和4个1单位的硬币，总共找回5个硬币。但最优的解答是3个5单位面值硬币。
贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题一种思路。
永远没有最好的算法，只有最适合的算法，我们选用贪心算法的原因就是因为它能够满足当前的需要并且比其他算法更加简单。

概念

贪心算法并不是整体最优考虑，它所做出的选择只是在某种意义上的局部最优（总是做出在当前看来是最好的选择）。这种局部最优选择并不能保证总能获得全局最优解，但它通常可以获得较好的近似最优解。
贪心算法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，不管将来有什么结果，这个选择不会改变。
贪心算法一般在开始策略选择前会进行排序，排好序后就进行最优化选择。