找零问题

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品,请问最少他会收到多少硬币?

解析1:数学方法。%为取余,/为取商

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int total = 1024;
        int cost = sc.nextInt();//总容量
        int a = (total - cost)/64;//12
        int b = ((total - cost)%64)/16;//3
        int c = (((total - cost)%64)%16)/4;
        int d = (((total - cost)%64)%16%4)/1;
        System.out.println(a+b+c+d);
    }
}

解析2:1,dp[i]为找零i所需的最小硬币数。2,初始化全部为i(最大值,找零1硬币的) 3,递推关系,dp[i]=min(dp[i],dp[i-num[j]]+1)

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int total = 1024;
        int cost = sc.nextInt();//总容量
        int change = total - cost;
        int[] dp = new int[change+1];
        for(int i = 1;i<=change;i++){
            dp[i] = i;
        }
        int[] num = {1,4,16,64};
        for(int i=1;i<=change;i++){
            for(int j=0;j<4;j++){
                if(i>=num[j]){//当找零要大于面额时
                     dp[i] = Math.min(dp[i],dp[i-num[j]]+1);
                } 
            }
        }
        System.out.print(dp[change]);
    }
}
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:11
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务