当前页面: 开发资料首页 → J2SE 专题 → 一个简单的找零钱问题

一个简单的找零钱问题

摘要: 一个简单的找零钱问题

请找出一种方案使找得的零钱个数最少，比如商店要给我找3.68元的零钱，应该是：两元1张，一元1张，五角1个，一角1个，五分1个，两分1个，一分1个。一共7张钱。
我的想法是，定义
int a,b,c,d,e,f,g;
double money = 3.68;
2*a + 1*b + 0.5*c + 0.1*d + 0.05*e + 0.02*f + 0.01*g = money;
System.out.println("2元的"+a+"张");
System.out.println("1元的"+b+"张");
..
好象这个想法不对，大哥些有什么高招嘛~？
先谢了~

---

class Money
{
public static void main(String[] args)
{
double money=3.68;
int count=0;
double[] arr = {2,1,0.5,0.2,0.1,0.05,0.02,0.01};
for(int i=0;i while((money-arr[i])>0){
count++;
}
System.out.println(arr[i]+"元的"+count+" 张")；
count=0;
}
}
}

---

补充一下

class Money
{
public static void main(String[] args)
{
double money=3.68;
int count=0;
double[] arr = {2,1,0.5,0.2,0.1,0.05,0.02,0.01};
for(int i=0;i while((money-arr[i])>0){
count++;
}
if(count!=0)
System.out.println(arr[i]+"元的"+count+" 张")；
count=0;
}
}
}

---

为什么一运行这个程序就卡的很呢？
好像没显示出来，什么都没显示。

---

再试试补充的~：）

---

error
没有结果输出啊
死循环？

---

我程序执行没问题，就是显示不出结果，你的想法我明白了~从大到小搜索
记录输出COUNT
我对数组的概念还比较模糊，不好修改这个程序

---

可用传统的思想解决：

背包问题 -> 贪心算法

---

package csdn;


class Money
{
public static void main(String[] args)
{
double money=3.68;
double count=0;
int i=0;
double[] arr = {2,1,0.5,0.2,0.1,0.05,0.02,0.01,0};
boolean notenough = true;
while(notenough){
System.out.println("放"+arr[i]+"元的");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
count = count +arr[i];
System.out.println("现在有"+count+"元");
if(count>money){
count=count-arr[i];
i++;
System.out.println(arr[i]+"元超过总数，删了！");
}

if(count==money){
notenough=false;
}

}
}
}
我写的，精度上有点问题，count==money 总不能相等
不知道怎么改了 。。。

---

干脆用整数模拟算了,都折算成单位:分
修改下3楼的代码
class Money
{
public static void main(String[] args)
{
int money=368;
int count=0;
int[] arr = {200,100,50,20,10,5,2,1};
for(int i=0;i while((money-arr[i])>0){
count++;
}
if(count!=0)
{
if(arr[i]>99)
System.out.println(arr[i]/100+"元的"+count+" 张")；
else if(arr[i]>9)
System.out.println(arr[i]/10+"角的"+count+" 张")；
else
System.out.println(arr[i]+"分的"+count+" 张")；

}
count=0;
}
}
}

---

再修改下~~~

while((money-arr[i])>0)
{
count++;
money-=arr[i];
}

---

定义一个数组
int[] a=new int[14];
int total=368;
a[0]=200，a[2]=100,a[4]=50,a[6]=10,a[8]=5,a[10]=2,a[12]=1;
for(int i=1;i<14;i+=2){
a[i]=total/a[i-1];
total=total mod a[i-1]
}
这样，数组里偶数下标的为钱的数额，继续下标的为张数。

---

想要输出什么格式的自己随便

---

haisenmai(我应该做得到)
的算法精度与问题，不断循环。
redduke1202()
经过修改的问题已经接近正确答案了~只少最后一分
而且总是少一分钱

---

我弄懂了~
把redduke1202()程序中的
while((money-arr[i])>0)改成
while((money-arr[i])>=0)就完美了~
谢谢大家咯

---

class Money
{
public static void main(String[] args)
{
double money=3.68;
int count=0;
double[] arr = {2,1,0.5,0.2,0.1,0.05,0.02,0.01};
for(int i=0;i while((money-arr[i])>0){
count++;
money-=arr[i];//加这一句
}
} if(count!=0)
System.out.println(arr[i]+"元的"+count+" 张")；
count=0;
}
}
}
这样结果出来的是结算你输入的钱，能换几张如输入2元出来是的一张2元的，2张1元...

---