首页 > 试题广场 >

日本旅行

[编程题]日本旅行

热度指数：1168 时间限制：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

输出

算法知识视频讲解

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var a,b,c,d,e,f,x int
    fmt.Scan(&a,&b,&c,&d,&e,&f,&x)
    arr:=[][]int{[]int{1,a},[]int{5,b},[]int{10,c},[]int{50,d},[]int{100,e},[]int{500,f}}
    ans:=-1
    var dfs func(int,int,int)
    dfs=func(sum int,tot int,idx int){
        if ans!=-1{
            return
        }
        if sum>=x{
            if sum==x{
                ans=tot
            }
            return
        }
        for i:=idx;i>=0;i--{
            if arr[i][1]==0{
                continue
            }
            sum+=arr[i][0]
            tot++
            arr[i][1]--
            if arr[i][1]==0{
                dfs(sum,tot,i-1)
            }else{
                dfs(sum,tot,i)
            }
            sum-=arr[i][0]
            tot--
            arr[i][1]++
        }
    }
    dfs(0,0,len(arr)-1)
    if ans==-1{
        fmt.Print("NOWAY")
    }else{
        fmt.Print(ans)
    }
}

发表于 2023-03-19 12:42:00 回复(0)