贪心算法硬币

⑴ 贪婪算法几个经典例子

问题一：贪心算法的例题分析 例题1、[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg价值 10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();输出一个解 return; } for(i=0; i>

问题二：收集各类贪心算法（C语言编程）经典题目 tieba./...&tb=on网络的C语言贴吧。 全都是关于C的东西。

问题三：几种经典算法回顾 今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | >

问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢 贪心算法的名词解释
ke./view/298415
第一个贪心算法 （最小生成树）
ke./view/288214
第二个贪心算法 （Prim算法）
ke./view/671819
第三个贪心算法 （kruskal算法）
ke./view/247951
算法都有详细解释的

问题五：求 Java 一些经典例子算法 前n项阶乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i 问题六：关于编程的贪心法 定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi>

问题七：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 问题八：分治算法的应用实例 下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] >

问题九：回溯算法的典型例题 八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

问题十：什么是算法，都什么，举个例子，谢谢 算法就是解决问题的具体的方法和步骤，所以具有以下性质：
1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决）
2、确切性：步骤必须明确，说清楚做什么。
3、输入：即解决问题前我们所掌握的条件。
4、输出：输出即我们需要得到的答案。
5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。
算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。

⑵ 算法09-贪心算法

贪心算法与动态规划的不同在于它对每个子问题的解决方案都作出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

很多情况下，可以在某一步用贪心算法，全局再加一个搜索或递归或动态规划之类

贪心法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。然而对于工程和生活中的问题，贪心法一般不能得到我们所要求的答案。
一单一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

当硬币可选集合固定:Coins = [20,10,5,1],求最少几个硬币可以拼出总数。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面这些硬币依次是后面硬币的整数倍，可以用贪心法，能得到最优解，

贪心法的反例
非整除关系的硬币，可选集合:Coins = [10,9,1],求拼出总数为18最少需要几个硬币？
最优化算法:9 + 9 = 18 两个9
贪心算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八个1

简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。这种子问题最优解成为最优子结构。
贪心算法与动态规划的不同在于它对每个子问题的最终方案都作出选择，不能回退。
动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：
如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：
-2 ：向左转 90 度
-1 ：向右转 90 度
1 <= x <= 9 ：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点 obstacles[i] = (xi, yi) 。
机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。
返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 5 ，则返回 25 ）
注意：
北表示 +Y 方向。
东表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：[5,5,10]
输出：true
示例 3：
输入：[10,10]
输出：false
示例 4：
输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2

⑶ 跪求pascal硬币找零问题！！！

这是一道比较简单的二维动态规划题。
数组b[0..200000,0..50]:boolean; '注意这点开20W，或者17W也可以。
fillchar(b,sizeof(b),0);
b[0,0]=1;
这是开始。
然后读入；
用a[1..50]为硬币的面额。
for i:=1 to 50 do
for j:=0 to 100000 do
for k:=1 to 50 do
if b[j,k] then b[j+a[i],k+1]:=true; 就是说假如用k个硬币，能组成 j 这种面额，那么加上我的这种第i张硬币，也可以所以就b[j+a[i],k+1]:=true；
OK。这就是状态转移方成
然后 s:=0; '记录是否有结果的变量s
for i:=1 to T do
if b[N,i] then
begin
s:=1;
ans:=i;
break; 可以中断循环了；
end;
至于另一种输出，不用教了吧！

现在编程又不保送了，还学他干什么，之前废寝忘食学了8个月，一失误，没保送，回去都已经高三很晚了，追悔莫及。

⑷ (三) 贪心算法

贪心算法的思想非常简单且算法效率很高，在一些问题的解决上有着明显的优势。

假设有3种硬币，面值分别为1元、5角、1角。这3种硬币各自的数量不限，现在要找给顾客3元6角钱，请问怎样找才能使得找给顾客的硬币数量最少呢？

你也许会不假思索的说出答案：找给顾客3枚1元硬币，1枚5角硬币，1枚1角硬币。其实也可以找给顾客7枚5角硬币，1枚1角硬币。可是在这里不符合题意。在这里，我们下意识地应用了所谓贪心算法解决这个问题。

所谓贪心算法，就是 总是做出在当前看来是最好的选择(未从整体考虑) 的一种方法。以上述的题目为例，为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可能地选择面值大的硬币。因此，下意识地遵循了以下方案：
（1）首先找出一个面值不超过3元6角的最大硬币，即1元硬币。
（2）然后从3元6角中减去1元，得到2元6角，再找出一个面值不超过2元6角的最大硬币，即1元硬币。
（3）然后从2元6角中减去1元，得到1元6角，再找出一个面值不超过1元6角的最大硬币，即1元硬币。
（4）然后从1元6角中减去1元，得到6角，再找出一个面值不超过6角的最大硬币，即5角硬币。
（5）然后从6角中减去5角，得到1角，再找出一个面值不超过1角的最大硬币，即1角硬币。
（6）找零钱的过程结束。
这个过程就是一个典型的贪心算法思想。

贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的 局部最优解 ，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解。但其解必然是最优解的很好近似解。）

贪心算法没有固定的算法框架，算法设计的关键是 贪心策略的选择 。选择的贪心策略必须具备无后效性。

贪心策略 适用的前提 是：

严格意义上讲，要使用贪心算法求解问题，该问题应当具备以下性质：

注意 ：对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。

因此， 选择能产生问题最优解的最优量度标准是使用贪婪算法的核心 。

实际上，贪心算法 适用的情况很少 。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

最优解问题大部分都可以拆分成一个个的子问题(多阶段决策问题)，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。

贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。

动态规划方法代表了这一类问题的一般解法， 自底向上 构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。

而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始( 自顶向下 )，选择最优的路，一直走到底就可以了。

一个问题分为多个阶段，每个阶段可以有n种决策，各个阶段的决策构成一个决策序列，称为一个策略。
这两种算法都是选择性算法，在进行决策的选择时：

前提是这个问题得具有贪心选择性质，需要证明(数学归纳法(第一、第二))，如果不满足那就只能使用动态规划解决。(一旦证明贪心选择性质，用贪心算法解决问题比动态规划具有更低的时间复杂度和空间复杂度。)

从范畴上来看：
Greedy ⊂ DP ⊂ Searching （贪心是动规的特例）
即所有的贪心算法问题都能用DP求解，更可以归结为一个搜索问题，反之不成立。

贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。但是贪心算法并不是对所有的问题都能得到整体最优解或最理想的近似解，与回溯法等比较，它的适用区域相对狭窄许多，因此正确地判断它的应用时机十分重要。

一步一步地进行，常 以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况 ，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

它采用 自顶向下 ，以 迭代 的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以 贪心法不需要回溯 。

【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条最短路径。

【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。

⑸ 找零钱问题的贪心算法

问题描述：
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）
问题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱方案

⑹ 收集各类贪心算法（C语言编程）经典题目

举个例子,假如你买东西，老板需要找给你99分钱，他有上面面值分别为25分，10分，5分，1分的硬币（都是假如，不符合实际），他得找你3个25分，2个10分的，4个1分的才为最佳方案！
用贪心算法编写程序实现！
main()
{
int
i,a[5],b[4],c[4];
/*
define
the
type
of
the
money*/
a[1]=25;
a[2]=10;
a[3]=5;
a[4]=1;
printf("please
input
you
money
(fen):\n");
scanf("%d",&b[0]);
for
(i=1;i<=4;i++)
{
b[i]=b[i-1]%a[i];
/*take
n
25
off
and
money
left*/
c[i]=(b[i-1]-b[i])/a[i];
/*
n
*/
printf("%d
is
%d\n",a[i],c[i]);
}
getch();
}

⑺ 背包问题

我们老师写的，看看吧

第三题，采药。这道题还是有难度的。基本解决思路有几种，贪心，模拟和动态规划。贪心算法能够解决举例的数据，但是测试数据则无法通过。模拟算法，可以通过30%的数据，即数据小与10个一下的测试数据。而对于100%的测试数据则严重超时无法计算。动态规划算法，解决较快，而且有效。

给出几种算法的大概思路，引导学生用三种算法完成这道题，体会算法的不同。

（1）贪心

program medic(input,output);

var f1,f2:text;

med_t:array[1..100] of integer;

med_v:array[1..100] of integer;

med:array[1..100] of real;

i,j,k,time,z,vale:integer;

zz:real;

begin

assign(f1,'medic.in');

assign(f2,'medic.out');

reset(f1);

rewrite(f2);

read(f1,time,j);

for i:=1 to j do

begin

read(f1,med_t[i],med_v[i]);

med[i]:=med_v[i]/med_t[i];

end;

for i:=1 to j-1 do{排序}

for k:=i+1 to j do

if med[i]<med[k] then begin z:=med_t[i];

med_t[i]:=med_t[k];

med_t[k]:=z;

z:=med_v[i];

med_v[i]:=med_v[k];

med_v[k]:=z;

zz:=med[i];

med[i]:=med[k];

med[k]:=zz;

end;

vale:=0;

for i:=1 to j do

begin

if med_t[i]<=time then begin

vale:=vale+med_v[i];

time:=time-med_t[i];

end;

if time=0 then break;

end;

write(f2,vale);

close(f1);

close(f2);

end.

上面是一个用贪心算法完成的习题。但是，我们很容易找到贪心算法的反例，而且贪心算法是只能在局部最优的基础上，找出整体次优的解法。所以它很难适合现代竞赛的要求，但是是否贪心算法就毫无用处呢？其实不然，在现实生活中，因为贪心算法是最接近人们思维方式的算法，所以在设计很多方面的问题（特别是经济方面的问题时，有很大的应用）。下面我们阐述一下有关贪心算法的一个重要应用——找零钱问题。

引入到硬币题中，我们可以为国家货币发行机关制定这样的假设：每次找零要求硬币数最小。

那么由此产生下面这些想法：

1，首先究竟贪心法的正确率怎么样？

事实和理论都已经证明，贪心法是一种渐近最优解，它未必是最优的解。事实确实是这样，考虑下面一种硬币面值组合1、3、4，当需要找零6的时候，贪心算法会按照4、1、1的方案，而事实上，3、3的方案才是最优解。那么我们马上会想到，是不是最优解会在最大面值和第二面值两者之一产生呢？

事实也证明这也只是猜想，考虑1、8、9、11这四种面值的硬币，要找零24的时候，首先产生解11、11、1、1，然后是解9、9、1、1、1、1、1、1，而实际上8、8、8才是最优解。

于是我们可以知道，这种机制是没有办法产生确定的最优解的。

2，接下来的问题是：要满足怎么样条件的面值组合，才能够在所有情况下能用贪心法来求解呢？

首先考虑我们实际存在的硬币组合1、2、5，几乎所有的情况下，它都不会造成误解，

1=1

2=2

3=1+2

4=2+2

5=5

6=1+5

7=2+5

8=1+2+5

9=2+2+5

那我们再来考虑1、2、4这个组合

1=1

2=2

3=1+2

4=4

5=1+4

6=2+4

7=1+2+4

8=4+4

9=4+4+1

我们可以发现，为了表现1-9这9种金额，1、2、4和1、2、5的平均找零硬币个数是相等的。

如果我们在1、2、4中再添加一个8（这是很容易让人联想到的），会不会有什么新奇的结果呢？

事实上，如果我们没有10元钞票的话，添加一个8元的钞票确实能够减少平均找零硬币个数，但不幸的是，我们使用十进制，所以加入一个8元的面值硬币对我们并没有什么太大的显着改进。但是不可否认，从这一点上我们可以发现一些规律。

3，考虑完上述数学逻辑上的问题以后，我们把目光再放回到实际的问题上，我们已经制定了1、2、5的组合策略，现在让我们来想一想，为什么这个策略被选中了呢？

那是因为（正如上文已经说过的）我们使用的十进制，因此在124与125这类的面值都能够很好的满足贪心算法的前提下，我们当然会更愿意选择125这种方案，因为i10=5*2，更加让人心里觉得舒服。

因此，我们可以把硬币面值制定策略所要遵循的规则总结为：必须满足贪心算法（因为大多数人可以使用这种比较少费脑子的方法进行计算），必须在心理上尽量满足人们对于十进制运算的方便性考虑（这也是125方案被选中的原因）

(2)模拟

program medic_moni;

uses crt;

var

fi,fo:text;

i,j,k,b:integer;

a:array[1..105] of 0..1;

tt,vv:array[1..100] of integer;

t,m:integer;

total1:integer;

value,max,time:longint;

begin

clrscr;

value:=0;max:=0;

assign(fi,'medic.in');

reset(fi);

assign(fo,'medic.out');

rewrite(fo);

read(fi,t);

read(fi,m);

readln(fi);

for i:=1 to m do

begin

read(fi,tt[i]);

read(fi,vv[i]);

readln(fi);

end;

for i:=1 to m do

a[i]:=0;

repeat

k:=m;

while (a[k]=1) do

begin

a[k]:=0;

dec(k);

end;

a[k]:=1;

time:=0;

value:=0;

for j:=1 to m do

begin

time:=time+tt[j]*a[j];

value:=value+vv[j]*a[j]

end;

if (time<=t) and (value>max) then

max:=value;

total1:=0;

for i:=1 to m do

if a[i]=1 then

inc(total1);

until total1=m;

writeln(fo,max);

close(fi);

close(fo);

end.

（3）动态规划

program medic;

uses crt;

var

fi,fo:text;

tt,vv:array[0..200] of integer;

dp:array[0..1005,0..105] of integer;

t,m:integer;

i,j:integer;

a,b:integer;

begin

clrscr;

assign(fi,'medic.in');

reset(fi);

assign(fo,'medic.out');

rewrite(fo);

read(fi,t);

read(fi,m);

readln(fi);

for i:=1 to m do

begin

read(fi,tt[i]);

read(fi,vv[i]);

readln(fi);

end;

for i:=1 to t do

begin

for j:=1 to m do

begin

a:=dp[i][j-1];

if i>=tt[j] then

begin

b:=dp[i-tt[j]][j-1]+vv[j];

if b>a then

a:=b;

end;

dp[i][j]:=a;

end;

end;

writeln(fo,dp[t][m]);

close(fi);

close(fo);

end.

⑻ 贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么怎样说明一个问题具有贪心选择呢

一般都是要最省事的比如
设有n中不同面值的硬币，个硬币的面值春雨数组T[1：n]中，现在要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意签署0<=m<=20001，设计一个用最少硬币找钱m的方法。

用贪心算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。这样最少
程序实例
#include<stdio.h>

void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;

}

for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d张\n",T[i],coins[i]);
printf("\n");
}

⑼ 贪心算法(硬币找零问题)

小Q手上有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量 少的硬币，但是要能组合出 1 到 m 之间的任意值。输入的第一行为两个整数： m 和 n ，他们的意义如题目描述。 接下来的 n 行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值。输出的最少需要携带的硬币数量，如果无解则输出 -1 。
50% 的数据： 1<=n<=10 ， 1<=m<=10^3 ；
100% 的数据： 1<=n<=100 ， 1<=m<=10^9 ；

数据量很大，dp不好做，也不好压缩，应该采用贪心的思路。首先如果没有面值为 1 的硬币必定无法满足要求可以直接输出 -1 ，接下来考虑贪心策略，设想如果能够组合出 1 到 5 之间的任何数值，只要一个 6 的硬币就能组合出 1 到 11 的任意值，既如果当前能够组合出 1 到 n 的硬币，再加入一个 n+1 面值的银币就能组合出 1 到 n+n+1 的所有面值。所以基本思路就是用一个变量 cur 存储当前能表示的面值，将硬币排序，从大往小找到第一个小于等于 cur+1 的硬币，硬币数加一同时更新 cur ，当 cur 大于 m 时输出。

⑽ 数据结构之贪心算法

贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。
贪婪算法：当下做局部最优判断，不能回退
（能回退的是回溯，最优+回退是动态规划）
由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求
结果不特别精确的问题
注意：当下是最优的，并不一定全局是最优的。举例如下：

有硬币分值为10、9、4若干枚，问如果组成分值18，最少需要多少枚硬币？
采用贪心算法，选择当下硬币分值最大的：10
18-10=8
8/4=2
即：1个10、2个4，共需要3枚硬币
实际上我们知道，选择分值为9的硬币，2枚就够了
18/9=2
如果改成：

背包问题是算法的经典问题，分为部分背包和0-1背包，主要区别如下：
部分背包：某件物品是一堆，可以带走其一部分
0-1背包：对于某件物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况。
部分背包问题可以用贪心算法求解，且能够得到最优解。
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，可以带走某件物品的一部分，请问：他应该选择哪些物品？
假设背包可容纳50Kg的重量，物品信息如下表：

将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略，单位重量的价值排序： 物品A > 物品B > 物品C
因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部分.....

在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)

优点：性能高，能用贪心算法解决的往往是最优解
缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的

针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）
大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明
在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解