Java貪欲思想

「貪欲」の字といえば、邪悪な言葉で、和
今日あなたは貪欲になって、明日1つの刑務所はあなたを包んで、古今を見渡して、どれだけの豪傑が“貪欲”と解けない縁を結んで、ほほほ、遠くまで引き延ばしました.
この貪欲な行為はアルゴリズムの中でも指導思想となっている.つまり、貪欲なアルゴリズムが行った選択は当時の環境の下で最もよく、深いと言えばそれはある種のものにすぎない.
意味上の局所最適解であるが,必ずしもグローバル最適解とは限らず,この場合最適解に近づくことが多い.
一:長所
前述したように、貪欲は現在の環境下の最適解を求めるだけで、全体の最適解を追及するのではなく、貪欲は全体の最適解を求めるために様々な案を列挙することを避ける.
費やされた時間.
二:問題
①貪欲に得られる解が全体的に最も優れているとは保証できない.
②最大解と最小解を求める問題には使用できません.
③いくつかの制約条件を満たす実行可能な解の範囲しか求められない.
三:ケース
実は欲張りといえば、基本的に「リュックサック問題」に言及しますが、ここでは「小銭を探す問題」を挙げます.はい、小銭を探す問題は私たちの生活の中で生きている欲張りアルゴリズムです.
例えば、私は「康さんがインスタントラーメンを1バレルください」を買って、銀10両、インスタントラーメン3.8両をあげました.
私に最低枚の貨幣を探すために、いつも私がmmに1枚あげることができなくて、mmは私に十数枚あげて、そのようにmmはかわいがることができます.
このときmmが提供する案は,5元1枚,1元1枚,2角1枚である.
おしゃべりは言わないで、コードをつけます:

package com.jiaozg.algorithm.feibonaqie;

import java.util.Scanner;

import org.junit.Test;

public class Tanxin {
	
	public void getChange(float money) {  
		  
        int yuan100 = 0, yuan50 = 0, yuan20 = 0, yuan10 = 0, yuan5 = 0, yuan1 = 0, coin5 = 0, coin2 = 0, coin1 = 0;  
  
        /** 
         *            demo 
         */  
        while (money >= 100d) {  
            yuan100++;  
            money -= 100d;  
        }  
        while (money >= 50d) {  
            yuan50++;  
            money -= 50d;  
        }  
        while (money >= 20d) {  
            yuan20++;  
            money -= 20d;  
        }  
        while (money >= 10d) {  
            yuan10++;  
            money -= 10d;  
        }  
        while (money >= 5d) {  
            yuan5++;  
            money -= 5d;  
        }  
        while (money >= 1d) {  
            yuan1++;  
            money -= 1d;  
        }  
        while (money >= 0.5d) {  
            coin5++;  
            money -= 0.5d;  
        }  
        while (money >= 0.2d) {  
            coin2++;  
            money -= 0.2d;  
        }  
        while (money >= 0.1d) {  
            coin1++;  
            money -= 0.1d;  
        }  
        System.out.println("   ：");  
        if (yuan100 > 0) {  
            System.out.println("100     " + yuan100 + " ");  
        }  
        if (yuan50 > 0) {  
            System.out.println("50      " + yuan50 + " ");  
        }  
        if (yuan20 > 0) {  
            System.out.println("20      " + yuan20 + " ");  
        }  
        if (yuan10 > 0) {  
            System.out.println("10      " + yuan10 + " ");  
        }  
        if (yuan5 > 0) {  
            System.out.println("5       " + yuan5 + " ");  
        }  
        if (yuan1 > 0) {  
            System.out.println("1       " + yuan1 + " ");  
        }  
        if (coin5 > 0) {  
            System.out.println("5       " + coin5 + " ");  
        }  
        if (coin2 > 0) {  
            System.out.println("2       " + coin2 + " ");  
        }  
        if (coin1 > 0) {  
            System.out.println("1       " + coin1 + " ");  
        }  
    }  
  
    @Test  
    public void testTanxinSuanFa() {  
        while (true) {  
            System.out.println("   (   1 )：");  
            Scanner scanner = new Scanner(System.in);  
            float money = scanner.nextFloat();  
            getChange(money);  
        }  
    }  
}

出力結果:
お金を払ってください(正確に1角まで):
1688.8 
お釣りが必要:
100元16枚
50元で1枚
20元で1枚
10元で1枚
5元で1枚
1元3枚
5角1枚
2角1枚
1角1枚
しかし、78.6を入力すると出力が間違っているという問題を発見しました.
78.6
お釣りが必要:
50元で1枚
20元で1枚
5元で1枚
1元3枚
5角1枚
お金を払ってください(正確に1角まで):
一角が少なくなって、debugが一角と比較することを発見する時、その数は0.0999999999999プログラミングして、だから一角は出力していません
この問題の詳細を述べる
小数点以下の正確な計算
System.out.println(2.00 -1.10);//0.8999999999999999
上記の計算結果は0.9ではなく、一連の小数である.問題は1.1という数字がdoubleとして正確に表現できないため、プログラムが2から減算したdouble値に最も近いと表現されるが、この計算の結果は0.9に最も近いdouble値ではない.
一般に、問題は、すべての小数点数がバイナリ浮動小数点数で正確に表現できるわけではないことである.
バイナリ浮動小数点は、1.0を10の他の負のべき乗として表すことができないため、通貨計算には非常に不適切です.
問題を解決する第1の方法は、通貨の最小単位(分)を使用して、System.out.println(200-110);//90
2つ目の方法はBigDecimalを使用することですが、BigDecimal(String)コンストラクタを使用する必要があります.BigDecimal(double)で構築しないでください(floatまたはdouble型をStringに変換してBigDecimal(String)で構築することはできません.floatまたはdoubleをStringに変換すると精度が失われるためです).例えばnew BigDecimal(0.1)は、BigDecimal、すなわち0.100000000000000000 5551151231257827021813404541015625を返します.BigDecimalを正しく使用すると、プログラムは私たちが望む結果0.9を印刷することができます.
System.out.println(new BigDecimal("2.0").subtract(new BigDecimal("1.10")));//0.9
また、2つの浮動小数点数の大きさを比較する場合は、BigDecimalのcompareToメソッドを使用します.
参照先:http://blog.csdn.net/m13666368773/article/details/7531473