贪心-硬币分配

绝地灬酷狼 2023-07-17 09:49 2阅读 0赞

硬币问题  
问题描述：  
有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  
C2 = 2  
C10 = 1  
C50 = 3  
C100 = 0  
C500 = 2  
A = 620  
输出：  
6（500元硬币1枚，50元硬币2枚，10元硬币1枚，5元硬币2枚，合计6枚）

思路：为了尽量地减少硬币的数量，我们首先得尽可能多地使用500元硬币，剩余部分尽可能多地使用100元硬币，剩余部分尽可能多地使用50元硬币，剩余部分尽可能多地使用10元硬币，再剩余部分尽可能多地使用5元硬币，最后的部分使用1元硬币支付。  
也就是优先使用大面值的硬币。使用贪心算法

import java.util.Scanner;
    
    import com.sun.org.apache.bcel.internal.generic.FNEG;
    
    import jdk.internal.org.jline.utils.AnsiWriter;
    import sun.jvm.hotspot.runtime.StaticBaseConstructor;
    
    
    public class 牛排队 {
        
    	static int []cnts=new int[6];
    	static int []coins= {
        1,5,10,50,100,500};
    	public static void main(String[] args) {
        
    		Scanner scanner=new Scanner(System.in);
    		for(int i=0;i<6;i++) {
        
    			cnts[i]=scanner.nextInt();
    		};
    		int A=scanner.nextInt();
    		int rea=f(A, 5);
    		System.out.print(rea);
    	}
    	static int f(int A,int cur) {
        
    		if (A<=0) {
        
    			return 0;
    		}
    		if (cur==0) {
        
    			return A;
    		}
    		int coinValue=coins[cur];
    		int x=A/coinValue;
    		int cnt=cnts[cur];
    		int t=Math.min(x, cnt);
    		return t+f(A-t*coinValue, cur-1);
    		
    	}
    	
    }