贪心算法——只追求当前利益最大化

忘是亡心i 2023-06-08 03:23 2阅读 0赞

**贪心——只追求当前状态的利益最大化**  
题目一：

随机给你一个n元钱，向你购买m元的商品，要求用100元，50元，20元，10元，5元，1元的纸币找零（0<m<=n<2^30）,请输出最少用几张纸币。

import java.util.Scanner;
    public class tx1 { 
    	//随机给你一个n元钱，向你购买m元的商品，要求用100元，50元，20元，10元，
    	//5元，1元的纸币找零（0<m<=n<2^30）,请输出最少用几张纸币。
    	public static int []price= { 100,50,20,10,5,1};
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		int ans=0;
    		for(int i=0;i<price.length;i++) { 
    			ans+=(n/price[i]);
    			n%=price[i];
    		}
    		System.out.println(ans);
    	}
    }

题目二：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    public class tx2 { 
    	public static char c1[];
    	public static char c2[];
    	public static int count=0;
    	public static void change(int i) { 
    		if(c1[i]=='*') { 
    			c1[i]='@';
    		}else { 
    			c1[i]='*';
    		}
    	}
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		String coin=sc.nextLine();
    		String gold=sc.nextLine();
    		c1=coin.toCharArray();
    		c2=gold.toCharArray();
    		for(int i=0;i<c1.length;i++)
    		{ 
    			if(c1[i]!=c2[i])
    			{ 
    				change(i);
    				change(i+1);
    				count++;
    			}
    		}
    		System.out.println(count);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230531/0304d8beb76c4ed6bafda6e9681519a1.png