2013
11-12

# 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. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

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