分硬币问题(贪心)
import java.util.Scanner;/*硬幣問題* 有1元、5元、10元、50元、100元、500元的硬幣各C1、C5、C10、C50、C100、C500枚。* 現在要用這些硬幣來支付A元，最少需要多少枚硬幣？假定本題存在一中支付方案。* 限制條件：* 0≤C1,C5,C10,C50,C100,C500≤10的9次方* 0≤A≤10的9次方* * 輸入* C1=3,C5=2,C10=1,C50=3,C100=0,C500=2,A=620;* 輸出：* 6(500元硬幣1枚，50元硬幣2枚，10元硬幣1枚，5元硬幣2枚，合集6枚)* */
public class CoinMax
{public static int[] C = new int[6];public static int[] V = new int[] {1, 5, 10, 50, 100, 500};//硬幣的面值public static int A;public static void main(String[] args){Scanner cin = new Scanner(System.in);System.out.println("請依次輸入C1---C500的枚數：");for (int i = 0; i < 6; ++i){C[i] = cin.nextInt();}System.out.println("支付A元：");A = cin.nextInt();cin.close();solve();}public static void solve(){int ans = 0;for (int i = 5; i >= 0; --i){int t = Math.min(A / V[i], C[i]);++ans;if (t != 0)System.out.print(V[i] + "元" + t + "枚 , ");A -= t * V[i];}System.out.println("共" + ans + "枚");}
}
========================================Talk is cheap, show me the code=======================================
轉載于:https://www.cnblogs.com/lcy0515/p/9179834.html
總結
