首页 > 代码库 > HDU 1353 Exact Change Only

HDU 1353 Exact Change Only

2024-07-30 22:58:49   218人阅读




Exact Change Only

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 206    Accepted Submission(s): 64


Problem Description
Boudreaux reached over and shook awake Thibodeaux, who had dozed off somewhere in New Mexico. "Where we at?" Thibodeaux groggily yawned.

"Not in Vegas, I gua-ran-tee, but could you get my knapsack?" Boudreaux asked, gesturing to the worn, leather backpack in the back seat of their cherry red Ford Miata.

"Why, is there a problem?"

"Just hand me my knapsack, problem or not."

Thibodeaux complied, glancing up as Boudreaux slowed the car to a stop in a line of vehicles approaching a toll booth. "1.65??Exactchangeonly,"Thibodeauxreadtheyellowsignonthefrontofasmallwoodenbuildingoccupiedbyalonetollboothoperator."Ihavetoget1.65 in exact change?" Thibodeaux asked, digging through the knapsack, "all I have are ten quarters, four dimes, and three pennies. I don‘t have any nickels . . ."

"Just give me five of the quarters and the four dimes," Boudreaux replied, holding out his hand.

"Oh yeah," Thibodeaux said, handing over the coins, "that does add up to $1.65. I wish there were an easy way to figure out if you have an exact monetary amount, given a set of coins."

"Hmmm," Boudreaux shrugged, "sounds like a good programming problem."
 

Input
Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.

A single data set has 1 component:

Start line - A single line: 
         A B C D E

where: 
     A: (0.01 ≤ A ≤ 5.00) is a decimal number (to two decimal places) of a monetary amount. 
     B: (0 ≤ B ≤ 100) is an integer number of quarters (one quarter = 0.25).C:(0≤C≤100)isanintegernumberofdimes(onedime=0.10). 
     D: (0 ≤ D ≤ 100) is an integer number of nickels (one nickel = 0.05).E:(0≤E≤100)isanintegernumberofpennies(onepenny=0.01). 
 

Output
For each data set, there will be exactly one line of output. If there exists one or more subsets of the given coins whose values add up to the given monetary amount exactly, the output will be a single line in the form:

    A B C D

where A is the number of quarters, B is the number of dimes, C is the number of nickels, and D is the number of pennies, for the subset with the fewest number of coins. Otherwise, the output will be a single line with the statement:

    NO EXACT CHANGE
 

Sample Input
0.45 2 1 1 4
0.75 3 7 1 75
 

Sample Output
NO EXACT CHANGE
3 0 0 0



简直SB了。。。想着用多重背包来做。。背了一万年都没想到怎么做。。

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 150
using namespace std;
#define eps 0.000000001

int main()
{
    double v;
    double a,b,c,d;
    while(~scanf("%lf%lf%lf%lf%lf",&v,&a,&b,&c,&d))
    {
        int num1,num2,num3,num4;
        int ff=0;

        for(int i=0;i<=a;i++)
        {
            for(int j=0;j<=b;j++)
            {
                for(int k=0;k<=c;k++)
                {
                    for(int m=0;m<=d;m++)
                    {
                        if(fabs(v-(0.25*i+0.1*j+0.05*k+0.01*m))<=eps)
                        {
                            num1=m;
                            num2=k;
                            num3=j;
                            num4=i;
                            ff=1;
                            break;
                        }
                    }
                }
            }
        }

        if(ff)
        cout<<num4<<" "<<num3<<" "<<num2<<" "<<num1<<endl;
        else
        cout<<"NO EXACT CHANGE"<<endl;

    }
    return 0;
}





HDU 1353 Exact Change Only


联系
我们