「java贪心算法找零」java贪心算法几个经典例子
今天给各位分享java贪心算法找零的知识，其中也会对java贪心算法几个经典例子进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、贪心算法(硬币找零问题)
- 2、找零钱问题的贪心算法
- 3、如何证明找零钱问题的贪婪算法总能产生具有最少硬币数的零钱
- 4、【JS算法】贪心算法
- 5、找零钱问题 [贪心算法](java实现）
- 6、贪婪法算法，求找零的最优方案，即从面值最大的开始找零！面值为:100元，50元，10元，5元，1元，0.5,0.1
贪心算法(硬币找零问题)
小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 时输出。
找零钱问题的贪心算法
问题描述：
当前有面值分别为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中的面值存放不同面值的硬币的个数，即找钱方案
如何证明找零钱问题的贪婪算法总能产生具有最少硬币数的零钱
pre t="code" l="java" private static final int[] m = {100,50,20,10,5,2,1};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int f = scanner.nextInt();
int[] amount = new int[f];
for(int i = 0 ; i f;i++){
amount[i] = giveChange(scanner.nextInt());
}
for(int i = 0 ; i amount.length;i++){
System.out.println(amount[i]);
}
}
public static int giveChange(int n) {
int num=0;
for(int i=0;im.length;i++){
num+=n/m[i];
n=n%m[i];
}
return num;
}
【JS算法】贪心算法
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择
举个简单的贪心算法： 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。每位顾客只买一杯柠檬水，然后向你付
5 美元或10 美元或 20 美元。
你必须给每个顾客正确找零，注意，一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false
找零钱问题 [贪心算法](java实现）
public getMin{
public int MinNumber=0;
public int findMax(int[] a){
for(int i=0;ia.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(ab) flag=flase;
return flag;
}
public int getMinNumber(int[] M,int Money){
int[] findM=new int[M.length];
int index=0;
for(int i=0;iM.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;iMinNumber.length.i++){
System.out.println(MinNumber[i]+" ");
}
}
}
public static void main(String[] args){
new getMin().print(new getMin().Start());
}
没测试啊，有问题请勿喷，呵呵
贪婪法算法，求找零的最优方案，即从面值最大的开始找零！面值为:100元，50元，10元，5元，1元，0.5,0.1
我帮你把代码修改了一下
#includestdio.h#includestdlib.h
#define Max 8
void exchange(double,int[]);
double moneyValues[Max]={100,50,20,10,5,1,0.5,0.1};
int main(){
int i;
int store[Max]={0};
double money;
printf("Input money that you will exchange!:");
scanf("%lf",money);
double premoney=money;
exchange(money,store);
printf("%f \n",premoney);
for(i=0;iMax;i++){
if(store[i]0)
printf("%d : %f\n",store[i],moneyValues[i]);
}
return 1;
}
void exchange(double exmoney,int store[]){
int i;
for(i=0;iMax;i++) {
if(exmoneymoneyValues[i]) break;
}
while(exmoney0 iMax) {
if(exmoneymoneyValues[i]){
exmoney-=moneyValues[i];
store[i]++;
}else if(exmoney0.1 exmoney0.05){
store[Max-1]++;
break;
}
else i++;
}
return;
}
然后，我觉得有些地方你写得啰嗦了，帮你简化了一下
#includestdio.h#includestdlib.h
#define Max 8
void exchange(double,int[]);
double moneyValues[Max]={100,50,20,10,5,1,0.5,0.1};
int main(){
int i;
int store[Max]={0};
double money;
printf("Input money that you will exchange!:");
scanf("%lf",money);
exchange(money,store);
printf("%f\n",money);
for(i=0;iMax;i++){
if(store[i]0)
printf("%d : %f\n",store[i],moneyValues[i]);
}
return 1;
}
void exchange(double money,int store[]){
int i=0;
while(money0 iMax) {
if(moneymoneyValues[i]){
money-=moneyValues[i];
store[i]++;
}else if(money0.1 money0.05){
store[Max-1]++;
break;
}
else i++;
}
return;
}
关于java贪心算法找零和java贪心算法几个经典例子的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。