❶ 找零钱问题的贪心算法
问题描述：
当前有面值分别为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中的面值存放不同面值的硬币的个数，即找钱方案
❷ 贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么怎样说明一个问题具有贪心选择呢
一般都是要最省事的比如
设有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");
}
❸ 找零钱问题 [贪心算法](java实现）
public getMin{
public int MinNumber=0;
public int findMax(int[] a){
for(int i=0;i<a.length;i++){
if(a[i]==0) return a[--i];
}
return a[a.length-1];
}
public boolean Compare(int a,int b){
public boolean flag=true;
if(a>b) flag=flase;
return flag;
}
public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];
int index=0;
for(int i=0;i<M.length;i++){
boolean f = this.Compare(M[i],money)
if(f) findM[index++]=M[i];
}
int max = this.findMax(findM);
MinNumber++;
if((Money-max)!=0) {
getMinNumber(M,Money-max)
}
return MinNumber;
}
public int[] Start(){
System.out.println("请输入查询组数");
int group=System.in.read();
int[] M={1,2,5,10,20,50,100};
int[] Result = new Int[group];
int index=0;
while (group-- > 0){
System.out.println("请输入金额");
int money=System.in.read();
Result[index++] = getMinNumber(M,money);
MinNumber=0;
}
}
public void print(int[] MinNumber){
for(int i=0;i<MinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}
public static void main(String[] args){
new getMin().print(new getMin().Start());
}
没测试啊，有问题请勿喷，呵呵