首页 > 专题系列 > Java解POJ > POJ 2818 Making Change [解题报告] Java
2013
11-12

POJ 2818 Making Change [解题报告] Java

Making Change

问题描述 :

Grocery stores have long struggled with how to avoid long checkout lines that leave customers frustrated. The “10 item or less” express line has been a common technique, but many stores a now trying to do even better by featuring self-service checkout lines. Such a system needs to have a mechanism to give correct change to the customer at the end of the transaction.

Write a program that, given the amount of change in the machine, can determine the quantities of each type of coins to return to the customer while minimizing the total number of coins dispersed.

输入:

Input consists of one or more lines, each of the form:

Q D N P C


where Q is the number of quarters in the dispenser, D is the number of dimes, N the number of nickels, P the number of pennies, and C is the number of cents (0. . . 99) owed to the customer.

End of the input is signaled by a line of 5 zeros.

输出:

For each line of input data, your program should output either:

Dispense # quarters, # dimes, # nickels, and # pennies.

or

Cannot dispense the desired amount.

if it is not possible to dispense the exact amount.

样例输入:

5 9 9 9 37
0 9 9 9 37
10 10 10 0 37
1 3 0 10 30
1 3 6 10 30
0 0 0 0 0

样例输出:

Dispense 1 quarters, 1 dimes, 0 nickels, and 2 pennies.
Dispense 0 quarters, 3 dimes, 1 nickels, and 2 pennies.
Cannot dispense the desired amount.
Dispense 0 quarters, 3 dimes, 0 nickels, and 0 pennies.
Dispense 1 quarters, 0 dimes, 1 nickels, and 0 pennies.

解题代码:

/* @author: */
import java.util.Scanner;   
import java.util.Arrays;
public class Main {   
   

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int sum,a[]=new int[4],b[]=new int[4],sum1=0;
    while(true)
    {
       a[0]=sc.nextInt();
       a[1]=sc.nextInt();
       a[2]=sc.nextInt();
       a[3]=sc.nextInt();
       sum=sc.nextInt();
       if(a[0]==0 && a[1]==0 && a[2]==0 &a[3]==0 && sum==0)
         break;
       for(int i=0;i< 4;i++)
          b[i]=a[i];
       for(int i=0;i<=a[0] && i*25<=sum;i++)
       for(int j=0;j<=a[1] && j*10<=sum;j++)
       for(int x=0;x<=a[2] && x*5<=sum;x++)
       for(int y=0;y<=a[3] && y<=sum;y++)
         if(i*25+j*10+x*5+y==sum)
         {
              if(i+j+x+y<=b[0]+b[1]+b[2]+b[3])
              {
                 b[0]=i;
                 b[1]=j;
                 b[2]=x;
                 b[3]=y;   
                 sum1=1;                            
              }                       
         }
      if(sum1==0)
         System.out.printf("Cannot dispense the desired amount.\n");
      else
        System.out.printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n",b[0],b[1],b[2],b[3]);  
       sum1=0;  
    }
   }
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮