首页 > 试题广场 >

日本旅行

[编程题]日本旅行
  • 热度指数：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

输出

6
算法知识视频讲解
添加回答
pein531头像 pein531
贪心，先用面值最大的钱，然后用次大的......，在此过程中对A进行自减，看A最后能不能归零 
C1, C5, C10, C50, C100, C500, A = map(int, input().strip().split())
cnt = 0
while A >= 500:
    if C500:
        C500 -= 1
        A -= 500
        cnt += 1
    else:
        break
while A >= 100:
    if C100:
        C100 -= 1
        A -= 100
        cnt += 1
    else:
        break
while A >= 50:
    if C50:
        C50 -= 1
        A -= 50
        cnt += 1
    else:
        break
while A >= 10:
    if C10:
        C10 -= 1
        A -= 10
        cnt += 1
    else:
        break
while A >= 1:
    if C1:
        C1 -= 1
        A -= 1
        cnt += 1
    else:
        break
if A == 0:
    print(cnt)
else:
    print("NOWAY")

编辑于 2021-04-10 12:05:14 回复(0)
C/C++
海问香12138头像 海问香12138

其他语言永远也体会不到C语言的快乐（尤其是C++） 
#include <stdio.h>

int sum;
int money[6]={1,5,10,50,100,500};
int have[6];

int min(int x,int y);

int main()
{
	int i,t,ans=0;
	for(i=0;i<6;scanf("%d",have+i++));
	scanf("%d",&sum);
	for(i=5;i^EOF && sum;i--)
	{
		t = min(have[i],sum/money[i]);
		sum -= t * money[i];
		ans += t;
	}
	if(sum)
		puts("NOWAY");
	else
		printf("%d\n",ans);
	return 0;
}

int min(int x,int y)
{
	return x<y?x:y;
}

发表于 2019-08-19 10:22:50 回复(1)
Python
lx的流星头像 lx的流星 
while True:
    try:
        C1,C5,C10,C50,C100,C500,A=map(int,input().split(' '))
        #print(C1,C5,C10,C50,C100,C500,A)
        list1=[500,100,50,10,5,1]
        list2=[C500,C100,C50,C10,C5,C1]
        for i in range(6):#将硬币数为0的硬币值归0
            if list2[i]==0:
                list1[i]=0
        num=0
        while A>0 and len(list2)!=0:
            #print(A)
            max_num=list1[0]
            if max_num!=0:
                if A>=max_num:
                    num1=A//max_num
                    if num1<=list2[0]:
                        num+=num1
                        A-=max_num*num1
                        list1.pop(0)
                        list2.pop(0)
                    else:
                        num+=list2[0]
                        A-=max_num*list2[0]
                        list1.pop(0)
                        list2.pop(0)
                else:
                    list1.pop(0)
                    list2.pop(0)     
            else:
                list1.pop(0)
                list2.pop(0)
        if A==0:
            print(num)
        else:
            print('NOWAY')
    except:
        break
编辑于 2019-07-26 14:02:55 回复(0)
呼叫-鲸鱼船长头像 呼叫-鲸鱼船长
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int A,C1,C2,C3,C4,C5,C6,a,b,c,d,e,f;
    int sum;
    scanf("%d %d %d %d %d %d %d",&C1,&C2,&C3,&C4,&C5,&C6,&A);
    e = A/500;
    A = A%500;
    d = A/100;
    A = A%100;
    c = A/50;
    A = A%50;
    b = A/10;
    A = A%10;
    a = A/5;
    A = A%5;
    f = A;
    if((f <= C1)&&(a <= C2)&&(b <= C3)&&(c <= C4)&&(d <= C5)&&(e <= C6))
    {
        sum = a+b+c+d+e+f;
        printf("%d\n",sum);
    }
    else
        printf("NOWAY");
    return 0;
}

发表于 2019-04-09 21:37:04 回复(1)
ChessC头像 ChessC 
一开始么觉得直接dp解决吧，多重背包转成0-1背包解决，样例过了，但是跑的时候竟然内存超限。。。。
//最少需要的数目，dp问题,并且是0-1背包的变形，多重背包，那么两点，一是转化成0-1背包问题，之后处理即可
#include <iostream>
#include <vector>
const int MaxNum=1000000000;
using namespace std;
class Solution{
public:
    int CalNum(vector<int>& nums,int A){
        vector<int> value{1,5,10,50,100,500};
        vector<int> v; //转化成的0-1背包的数组
        for(int i=0;i<(int)nums.size();++i)
            for(int j=0;j<nums[i];++j)
                v.push_back(value[i]);
        return solve(v,A);
    }
private:
    int solve(vector<int>& v,int A){
        vector<int> dp(A+1,MaxNum); //dp解决
        dp[0]=0;
        for(int i=0;i<(int)v.size();++i)
            for(int j=A;j>=v[i];--j) //0-1背包逆序没有问题
                dp[j]=min(dp[j],dp[j-v[i]]+1);
        return dp[A]==MaxNum?-1:dp[A];
    }
};
int main(){
    int C1,C5,C10,C50,C100,C500,A;
    cin>>C1>>C5>>C10>>C50>>C100>>C500>>A;
    vector<int> nums{C1,C5,C10,C50,C100,C500};
    Solution sol;
    int res=sol.CalNum(nums,A);
    if(res==-1)
        cout<<"NOWAY";
    else
        cout<<res;
    return 0;
}
-------------------------------------
那就不用dp了，一点点从大往小减吧
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int C1,C5,C10,C50,C100,C500,A;
    cin>>C1>>C5>>C10>>C50>>C100>>C500>>A;
    vector<int> nums{C500,C100,C50,C10,C5,C1};
    vector<int> value{500,100,50,10,5,1};
    int cnt=0;
    for(int i=0;i<(int)nums.size() && A>0;++i){
        int index=A/value[i];
        index=min(index,nums[i]);
        A-=value[i]*index;
        cnt+=index;
    }
    if(A!=0)
        cout<<"NOWAY";
    else 
        cout<<cnt;
    return 0;
}

发表于 2019-02-27 13:30:26 回复(1)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int C[6],A;     int w[6] = {1,5,10,50,100,500};     while(cin>>C[0])     {         for(int i=1;i<=5;i++)             cin>>C[i];         cin>>A;         int cnt=0, p=5;         while(p>=0)         {             int t = A/w[p];             if(t<=C[p]){                 A -= t*w[p];                 cnt += t;             }else{                 A -= C[p]*w[p];                 cnt += C[p];             }             p--;                          }         if(A==0)             cout<<cnt<<endl;         else             cout<<"NOWAY"<<endl;     }     return 0;
}

发表于 2019-01-24 03:26:15 回复(0)
Go
小谷围做题家头像 小谷围做题家 
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)
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)
苏南霖头像 苏南霖
本题如果用动态规划，建议使用空间复杂度为O(n)的dp，二维dp容易堆溢出，这里给出基于贪心的思路 
import java.util.Scanner;

public class Main{
    public static void minMoney(int[] c, int A){
        int []money = {1,5,10,50,100,500};
        int sum = 0;
        for(int i=5;i>=0;i--){
            int tmp = A/money[i];
            if(tmp>c[i])    tmp = c[i];
            sum+=tmp;
            A -=tmp*money[i];
        }
        if(A==0) System.out.println(sum);
        else System.out.println("NOWAY");
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int[] c = new int[6];
        for(int i=0;i<6;i++){
            c[i] = in.nextInt();
        }
        int A = in.nextInt();
        minMoney(c,A);
    }
}


发表于 2021-04-10 15:57:48 回复(0)
Lich2020头像 Lich2020 
//运行时间：23ms
//占用内存：13416k
//本题可用dfs，但一定要注意递归的初始顺序和剪枝。

#include <iostream>

using namespace std;

int m[6] = {1, 5, 10, 50, 100, 500};
int c[6];
int result = 100000000;

void dfs(int yingbi, int cur, int a){

    if(result!=100000000){  //只要下面的循环是从大硬币开始，那么递归得到的第一个结果就是最优值，不必继续计算；
        return;
    }
    if(cur==a){
        result = yingbi;
    }
    if(cur>a){
        return;
    }

    int i;
    for(i=5;i>=0;i--){  //一定要先从大硬币开始；
        if(c[i]>0){
            c[i]--;
            dfs(yingbi+1, cur+m[i], a);
            c[i]++;
        }
    }

    return;
}

int main(){


    int a;
    while(cin >> c[0] >> c[1] >> c[2] >> c[3] >> c[4] >> c[5] >> a){

        result = 100000000;
        dfs(0, 0, a);

        if(result!=100000000){
            cout << result << endl;
        }
        else{
            cout << "NOWAY" << endl;
        }

    }
    return 0;
}
发表于 2020-03-31 10:30:01 回复(0)
Python
白色纯度头像 白色纯度
python3 
写代码力求简单通俗易懂，其次是时间和空间的优化。今天被华为秋招题目虐了，已经自闭了！尤其那个全组合，真的是气死我了！ 
def solve(c,num,money):
    res = 0
    for i in range(len(num)-1,-1,-1):
        while money>=num[i] and c[i]>0:
            money -= num[i]
            c[i] -= 1
            res += 1
    return res
if __name__=='__main__':
    c = list(map(int,input().split()))
    money = c[-1]
    num = [1,5,10,50,100,500]
    ans = solve(c[:-1],num,money)
    if ans==0:
        print('NOWAY')
    else:
        print(ans)


发表于 2019-09-07 23:46:18 回复(0)
奔跑的蛋蛋头像 奔跑的蛋蛋

贪心
感觉时间复杂度略高

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int[] a = {1, 5, 10, 50, 100, 500};
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < 6; i++) {
                map.put(a[i], in.nextInt());
            }
            int sum = in.nextInt();
            int cnt = 0;
            for (int i = 5; i >= 0; i--) {
                int value = map.get(a[i]);
                for (int j = 0; j < value; j++) {
                    sum -= a[i];
                    cnt++;
                    if (sum < 0) {
                        sum += a[i];
                        cnt--;
                        break;
                    }
                }
            }
            System.out.println(sum == 0 ? cnt : "NOWAY");
        }
        in.close();
    }
}
发表于 2019-05-26 14:09:25 回复(0)
C/C++
guandadashen头像 guandadashen 
#include <iostream>
using namespace std;

int main()
{
    int a, coins = 0;
    int c[6],unit[6] = {500,100,50,10,5,1};
    cin >> c[5] >> c[4] >> c[3] >> c[2] >> c[1] >> c[0] >> a;

    for(int i = 0; i < 6; i++)
    {
        if (c[i] >= a/unit[i])
        {
            coins += a/unit[i];
            a -= (a/unit[i])*unit[i];
        }
        else
        {
            coins += c[i];
            a -= c[i]*unit[i];
        }
        if(a == 0)
        {
            cout << coins;
            return 0;
        }
    }
    if (a > 0)
    {
        cout << "NOWAY";
    }
    return 0;
}

发表于 2019-04-19 16:56:02 回复(0)
OPPO学长头像 OPPO学长 
#include<iostream>
using namespace std;
int main()
{
    int c1,c5,c10,c50,c100,c500,A;
    cin>>c1>>c5>>c10>>c50>>c100>>c500>>A;
    int n1,n5,n10,n50,n100,n500;//每种货币需要数量
/*
    if((A/500)<c500)
        n500=0;
    else
        n500=A/500;
    A=A-n500*500;
  */
    if((A/500)<0||(A/500)>c500)
        n500=0;
    else
        n500=A/500;
    A=A-500*n500;

        if((A/100)<0||(A/100)>c100)
        n100=0;
    else
        n100=A/100;
    A=A-100*n100;


        if((A/50)<0||(A/50)>c50)
        n50=0;
    else
        n50=A/50;
    A=A-50*n50;


        if((A/10)<0||(A/10)>c10)
        n10=0;
    else
        n10=A/10;
    A=A-10*n10;

            if((A/5)<0||(A/5)>c5)
        n5=0;
    else
        n5=A/5;
    A=A-5*n5;


if(A<c1)
    n1=A;
    else
        cout<<"NOWAY"<<endl;

    cout<<n1+n5+n10+n50+n100+n500<<endl;

    return 0;
}

发表于 2019-04-09 16:54:44 回复(0)
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int a = Integer.parseInt(strs[strs.length - 1]);
        int[] c = new int[strs.length - 1], coin = {1, 5, 10, 50, 100, 500};
        for (int i = 0; i < strs.length - 1; i++) {
            c[i] = Integer.parseInt(strs[i]);
        }

        int res = 0;
        for (int i = 5, need; i >= 0 && a > 0; i--, res += need) {
            need = a / coin[i];
            if (need > c[i]) need = c[i];
            a -= coin[i] * need;
        }
        System.out.println(a == 0 ? res : "NOWAY");
    }
}

编辑于 2019-03-14 11:10:12 回复(0)
垂泽头像 垂泽 
/* 为保证数量最少，从500开始凑，500凑完，就用100凑，如此类推 */
import java.util.*;

public class Main { 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] money = {1, 5, 10, 50, 100, 500};
        int[] count = new int[6];
        for (int i = 0; i < 6; i++) {
            count[i] = in.nextInt();
        }
        int A = in.nextInt();
        int ans = 0;
        for (int i = 5; i >= 0 && A > 0; i--) {
            int c = A / money[i]; // 需要多少张
            if (count[i] < c) {  // 实际能给多少张
                c = count[i];
            }
            ans += c;
            A -= (c * money[i]); // 剩下的金额
        }
        // 若最后的金额不为0,则NOWAY
        if (A != 0) {
            System.out.println("NOWAY");
        } else {
            System.out.println(ans);
        }
    }
}

发表于 2019-02-22 18:54:19 回复(2)
Disconnect头像 Disconnect 
t = list(map(int,input().split()))
coin = [1,5,10,50,100,500]
c = t[:6]
A = int(t[-1])
index = 5
cnt = 0
while A>0:
    if index<0:
        break
    if c[index]>0:
        if coin[index]>A:
            index-=1
        else:
            if A-coin[index]>=0:
                A = A-coin[index]
                c[index]-=1
                cnt+=1
                if A==0:
                    break
            else:
                index-=1
    else:
        index-=1
if A==0:
    print(cnt)
else:
    print('NOWAY')

发表于 2019-02-18 12:26:54 回复(0)
提交观点

问题信息

动态规划
上传者：小小
难度：
17条回答 3062浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号