找零问题贪心算法

① 贪心算法，这个贪心到底是什么意思

贪心指目光短浅，只看到当前这一步的最优决策，而不考虑以后的决策。这样的算法只在特定的问题下是正确的。

② C语言，贪心算法，货币找零问题

贪心算法找零就是现实中从最大面额开始找的思路。不代表是最优解，只是算法之一。

由于面额输入顺序不定，我先对输入的面额进行降序排序。

下面代码：

#include <stdio.h>

#include <malloc.h>

int main()

{

int i,j,m,n,*ns=NULL,*cn=NULL,sum=0;

printf("请输入总金额m及零钱种类n："),scanf("%d",&m),scanf("%d",&n);

printf("请分别输入%d种零钱的面额： ",n);

if(!(ns=(int *)malloc(sizeof(int)*n))) return 1;

if(!(cn=(int *)malloc(sizeof(int)*n))) return 1;

for(i=0;i<n;i++) scanf("%d",&ns[i]);

//------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除）

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i];

//-------------------------------------------------------------------

for(i=0;i<n;i++)//贪心算法，从最大面额开始

if(m>=ns[i])

cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d张 ",ns[i],cn[i]);

printf(" 最少使用零钱%d张 ",sum);

return 0;

}

③ 贪心算法找零问题

贪心算法是什么东东？
两张2元加5角+1角

④ 找零钱问题的贪心算法

问题描述：
当前有面值分别为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中的面值存放不同面值的硬币的个数，即找钱方案

⑤ Python贪心算法

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。
顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。
我们可以从面值最大的硬币开始，然后依次递减（图1）。
首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。
贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报

⑥ 找零钱问题 [贪心算法](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());
}

没测试啊，有问题请勿喷，呵呵

⑦ 求找零钱问题和背包贪心算法问题（背包里物体可分解）C语言程序

分数太少了，第一个是动态规划，第二个是贪心，都挺简单的
还是给你写吧
第一题：
#include<stdio.h>
#include<memory.h>
int a[2000],b[200000],n,m,i,j;
int main()
{
scanf("%d",&n);//钱币种类
for (i=0;i<n;i++)
scanf("%d",&a[i]);//每个钱币的面值
scanf("%d",&m);//需要计算的钱币的面值
memset(b,0,sizeof(b));
for (i=0;i<n;i++)
b[a[i]]=1;
for (i=1;i<=m;i++)
for (j=0;j<n;j++)
if (i-a[j]>0)
if (b[i]==0)
{
if (b[i-a[j]]!=0)
b[i]=b[i-a[j]]+1;
}
else
{
if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i])
b[i]=b[i-a[j]]+1;
}
if (b[m]==0) printf("-1\n");//找不开输出-1
else printf("%d\n",b[m]);//可以找到交换策略，输出最小票数
return 0;
}

第二题：
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}

⑧ 找零问题 贪心算法何时为最优解

最快回答那个不懂别乱说，别误人子弟。 这题标准的贪心算法，甚至很多时候被当做贪心例题 要求平均等待时间，那么就得用 总等待时间 / 人数 所以只用关心总等待时间， 如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。

⑨ 编写程序，采用贪婪法编程实现人民币的找零

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
故：
#include <stdio.h>
int main()
{
int a[6]={100,50,20,10,5,1};//定义金数数目，忽视1块钱以下的。。
int money,tmpMoney=0;
scanf("%d",&money);//输入想要换算成零钱的值。
for(int i=0;i<6;i++){//由于上面数组有六个值。循环六次
while(money>=a[i]){//当钱额小于面值时退出循环
money-=a[i];//当前金额减去面值
tmpMoney++;//保存当前面值的张数
}
printf("%d元的张数为：%d\n",a[i],tmpMoney);
tmpMoney=0;//把这下一次的数量清零
}
}
想要找零设置角和分的可以，只要把类型改为float类。或把值*10倍

⑩ 贪婪法算法，求找零的最优方案，即从面值最大的开始找零！面值为:100元，50元，10元，5元，1元，0.5,0.1

我帮你把代码修改了一下

#include<stdio.h>#include<stdlib.h>

#defineMax8

voidexchange(double,int[]);

doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};

intmain(){

inti;

intstore[Max]={0};

doublemoney;

printf("Inputmoneythatyouwillexchange!:");

scanf("%lf",&money);

doublepremoney=money;

exchange(money,store);

printf("%f ",premoney);

for(i=0;i<Max;i++){

if(store[i]>0)

printf("%d:%f ",store[i],moneyValues[i]);

}

return1;

voidexchange(doubleexmoney,intstore[]){

inti;

for(i=0;i<Max;i++){

if(exmoney>moneyValues[i])break;

}

while(exmoney>0&&i<Max){

if(exmoney>moneyValues[i]){

exmoney-=moneyValues[i];

store[i]++;

}elseif(exmoney<0.1&&exmoney>0.05){

store[Max-1]++;

break;

}

elsei++;

}

return;

然后，我觉得有些地方你写得啰嗦了，帮你简化了一下

#include<stdio.h>#include<stdlib.h>

#defineMax8

voidexchange(double,int[]);

doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};

intmain(){

inti;

intstore[Max]={0};

doublemoney;

printf("Inputmoneythatyouwillexchange!:");

exchange(money,store);

printf("%f ",money);

for(i=0;i<Max;i++){

if(store[i]>0)

printf("%d:%f ",store[i],moneyValues[i]);

}

return1;

voidexchange(doublemoney,intstore[]){

inti=0;

while(money>0&&i<Max){

if(money>moneyValues[i]){

money-=moneyValues[i];

store[i]++;

}elseif(money<0.1&&money>0.05){

store[Max-1]++;

break;

}

elsei++;

}

return;