首页 > 试题广场 >

日本旅行

[编程题]日本旅行

热度指数：1209 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

楚乔、宇文玥和燕洵在日本旅行，经过了几天的游玩之后，钱包里出现了大量硬币，楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有1元、5元、10元、50元、100元和500元硬币各C1,C5,C10,C50,C100,C500枚。现在要用这些硬币来到自动贩卖机买价格为A的饮料，假设自动贩卖机所需的硬币金额必须是刚刚好，不能多也不能少，最少需要多少枚硬币？

限制条件

0≤ C1,C5,C10,C50,C100,C500≤1000000000

0≤A≤1000000000

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔，输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

输入描述:

依次输入C1,C5,C10,C50,C100,C500和A，以空格分隔

输出描述:

输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

示例1

输入

3 2 1 3 0 2 620

输出

算法知识视频讲解

Java

Sen🍓🍀

import java.util.Scanner;

// 贪心：从面额大的开始枚举😳 
// 感觉其他的for、while循环并不能列举所有情况
public class Main {
    private static boolean find = false;
    private static int res = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] coin = {1, 5, 10, 50, 100, 500};
        int[] cnt = new int[6];
        for (int i = 0; i < 6; i++) cnt[i] = in.nextInt();
        int A = in.nextInt();

        backtrack(coin, cnt, 5, A); // dfs

        if (find) System.out.print(res);
        else      System.out.print("NOWAY");
    }

    // 回溯
    private static void backtrack(int[] coin, int[] cnt, int k, int rest) {
        if (find || k < 0 || rest == 0) {
            if (rest == 0) find = true;
            return;
        }

        int i = Math.min(cnt[k], rest / coin[k]); // 开始选最多能兑换的个数
        for (; i >= 0; i--) {
            res += i;
            backtrack(coin, cnt, k - 1, rest - i * coin[k]);
            if (find) break;
            res -= i;
        }
    }
}

发表于 2025-04-22 19:05:08 回复(0)

Java

再向前一点

当硬币问题符合人民币的额度规则，即1、2、5、10这样的规则时，直接使用贪心算法即可，即从大到小进行选择一定为最优解。

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = 6;
        int[] v = new int[]{1,5,10,50,100,500};
        int[] w = new int[n];
        for(int i=0;i<n;i++)
            w[i] = in.nextInt();
        int target = in.nextInt();
        int res = 0;
        for(int i=n-1;i>=0 && target>0;i--){
            for(int j=0;j<w[i] && target>=v[i];j++){
                target-=v[i];
                res++;
            }
        }
        System.out.println(target==0?res:"NOWAY");
    }
}

发表于 2021-08-24 11:03:21 回复(0)