求一元钱换零钱算法的优化方法

cmooc 2007-02-02 11:15:15

问题：
将一元钱换成1分、2分、5分、1角、2角、5角的零钱若干，一共有多少种算法？

我最初写的算法要用到6层循环，但是这个应该是可以优化的
据说最终可以优化成一个公式
不知要怎么优化呢？
哪位可以给个具体点的思路
多谢各位咯！

我的代码如下：

#include <iostream.h>

void main()
{
int total=0;
for(int i=0;i<=100;i++)
for(int j=0;j<=50;j++)
for(int k=0;k<=20;k++)
for(int l=0;l<=10;l++)
for(int m=0;m<=5;m++)
for(int n=0;n<=2;n++)
if(i+2*j+5*k+10*l+20*m+50*n==100)
{
cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<m<<" "<<n<<" "<<"*";
total++;
}
cout<<total;
cin.get();
}

...全文

4150 66 打赏收藏转发到动态举报

写回复

用AI写文章

66 条回复

切换为时间正序

请发表友善的回复…

发表回复

saramand9 2010-09-02

打赏
举报

07年的帖子- -||

bingshanzhiling 2010-09-02

打赏
举报

怎么感觉和动态规划很像呢？达人显身解释一下吧

bingshanzhiling 2010-09-02

打赏
举报

按照母函数把x^100的系数计算出来呗。
公式上面有人列出来了。超过100次方的全去掉了。多项式乘法实现一下就可以了。好像是用链表可以实现

wizard_tiger 2010-09-02

打赏
举报

写一个c语言的



#include<stdio.h>

int main()

{

   int p1,p2,p3,p4,p5,p6;//分别表示1分2分5分1角2角5角

    int n=100//n为1元

   for(p2=0;p2<=n/2;p2++)

   for(p3=0;p3<=(n-2*P2)/5;p3++)

   for(p4=0;p4<=(n-2*p2-5*p3)/10;p4++)

   for(p5=0;p5<=(n-2*p2-5*p3-10*p4);p5++)

   for(p6=0;p6<=(n-2*p2-5*p3-10*p4-20*p5)/50;p6++)

         {

             p1=n-(2*p2+5*p3+10*p4+20*p5+50*p6);

             if(p1>=0)

               {

                   printf("1分=%d\t2分=%d\t5分=%d\t1角=%d\t2角=%d\t5角=%d\t",p1,p2,p3,p4,p5,p6);

               }

         }

   return 0;

}

请多指正！

aqxiebin 2010-09-01

打赏
举报

典型的背包问题。。。

wjz748305545 2010-04-17

打赏
举报

[Quote=引用 33 楼 mathe 的回复:]
一重循环就可以了。
//result = count(50x+20y+10z+5w+2u <=100)
//assuming 50x+20y+10z=10k,
//0 <=k <=10
//We get 5w+2u <=100-10k, 5x+2y <=k
//So the result is
//sum=0;
//for(k=0;k <=10……
[/Quote]
犀利啊

linkin1005 2010-04-16

打赏
举报

单纯形法

lzy18lzy 2010-03-30

打赏
举报

参照整数拆分方式，写的一个DP



#include<stdio.h>

#include<string.h>

#include<stdlib.h>



int DP[251][7];

int save[7] = {1,2,5,10,20,50,100};



int DFS(int num,int step)

{

	while(step>0 && num<save[step]) step--;



	if(DP[num][step] == 0)

 		DP[num][step] =  DFS(num,step-1) + DFS(num-save[step],step);



	return DP[num][step];

}



int main()

{

	int i,j;

	memset(DP,0,sizeof(int)*251*7);



	for(i = 0; i<= 6;i++)DP[0][i] = 1;

	for(i = 0; i<= 250;i++)DP[i][0] = 1;



//	freopen("test.txt","w",stdout);

	

	for(i = 1;i<=250;i++)

	{

		for(j = 6;j>=0;j--)

			if(i>=save[j])

				break;

		DFS(i,j);

		printf("%d %d\n",i,DP[i][j]);

	}



	return  0;

}

LeonTown 2010-03-30

打赏
举报

这个不是DP，是递归，
DP的话大概是：

vector<int> vec;

int fDP(int left)

{

	int cnt = 0;

	

	if(left-50 >= 0)

	{

		if(vec[left-50] == -1)

			vec[left-50] = fDP(left-50);

		cnt += vec[left-50];

	}

        //下面累计20，10等



	return cnt;

}

void fCaller()

{

	vec.resize(101);

	for(int i=0; i<vec.size(); ++i) vec[i] = -1;



	for(int i=0; i<=100; ++i)

	{

		fDP(i);

	}



	int cnt = vec[100];

}

[Quote=引用 57 楼 leontown 的回复:]
简单的想了个DP

C/C++ code
int f(int left)
{
if(left < 0)
return 0;
if(left == 0)
return 1;

int cnt = 0;
cnt += f(left - 50);
cnt += f(left - 20);
cnt……
[/Quote]

LeonTown 2010-03-30

打赏
举报

简单的想了个DP

int f(int left)

{

	if(left < 0)

		return 0;

	if(left == 0)

		return 1;



	int cnt = 0;

	cnt += f(left - 50);

	cnt += f(left - 20);

	cnt += f(left - 10);

	cnt += f(left - 5);

	cnt += f(left - 2);

	cnt += f(left - 1);



	return cnt;

}



void main()

{

   int cnt = f(100);

}

chensb666 2010-03-29

打赏
举报

Mark

leil 2008-11-07

打赏
举报

用递归吧
public class STest {

static int[] values={1,2,5,10,20,50};
static int j=0;

public static void main(String[] args) {
split(100,0,"");
}

public static void split(int n,int base,String result){
if(n<0) return;
if(n==0){
++j;
System.out.println(result+j+"种");
return;
}
for(int i=base;i<values.length;i++){
split(n-values[i],i,result+values[i]+"|");
}
}
}

xiaofengsheng 2008-11-06

打赏
举报

Mark

mrdone 2008-11-05

打赏
举报

靠，思想都有，就是实现的时候有些头大了，
好晕！看来要调整一天了。
zzZZZ

mrdone 2008-11-05

打赏
举报

靠，思想都有，就是实现的时候有些头大了，
好晕！看来要调整一天了。
zzZZZ

BusyCai 2008-10-21

打赏
举报

6楼正解。

bosshuyun 2007-03-13

打赏
举报

dynamic programming

static double res[100]={0};
static const int N=6;
static int a[N]={50,20,10,5,2,1};
static double CalChange(int val) {
if(val<0) return 0;
if(res[val]==0)
{
for(int i=0;i<N;i++) {
if(val>a[i])
{
double tmp=CalChange(val-a[i]);
res[val]+=tmp;
} else if(val==a[i])
res[val]+=1;
}
}
return res[val];
}

tesling 2007-03-09

打赏
举报

class _yuan
{
int total = 100;//单位分
int[] a = new int[] { 1,2,5,10,20,50};
public void count()
{
long begtime=DateTime.Now.Ticks;
Console.WriteLine("BeginTime:{0}", DateTime.Now.ToString("yyyy-MM-dd hh:mm:ss"));
int current1 = 0, current2 = 0, current3 = 0, current4 = 0,current5=0 ;
int x = 1;
for (int i = 0; i <= total / a[5]; ++i)
{
current1 = i * a[5];
for (int j = 0; j <= (total - current1) / a[4]; ++j)
{
current2 = j * a[4];
for (int k = 0; k <= (total - current1-current2) / a[3]; ++k)
{
current3 = k * a[3];
for (int l = 0; l <= (total - current1-current2-current3) / a[2]; ++l)
{
current4 = l * a[2];
for (int m = 0; m <= (total - current1 - current2 - current3-current4) / a[1]; ++m)
{
current5 = m * a[1];
Console.WriteLine("{0},{1}个五角,{2}个二角,{3}个一角,{4}个五分,{5}个二分,{6}个一分",x,i,j,k,l,m,total-current1-current2-current3-current4-current5);
x++;
//if (x % 100 == 0)
//Console.ReadLine();

}

}
}
}
}
Console.WriteLine("EndTime:{0}", DateTime.Now.ToString("yyyy-MM-dd hh:mm:ss"));
Console.WriteLine("TimeConsume:{0}ms",DateTime.Now.Ticks-begtime);
}
}
4562种

lovingpig 2007-03-09

打赏
举报

楼上renzaijiang() 兄弟的算法有点小问题
我改了下

public static void main(String[] arg) {
int total = 0;
for(int i=0;i<=2;i++)
for(int j=0;j<=100/20;j++){
if(50*i+20*j>100){
continue;
}
for(int k=0;k<=10;k++){
if(50*i+20*j+10*k>100){
continue;
}
for(int l=0;l<=20;l++){
if(50*i+20*j+10*k+5*l>100){
continue;
}
for(int m=0;m<=50;m++){
if(50*i+20*j+10*k+5*l+2*m>100){
continue;
}
for(int n=0;n<=100;n++)
{
if(i*50+j*20+k*10+5*l+2*m+n==100){
System.out.println(i+"*50+"+j+"*20+"+k+"*10+"+l+"*5+"+m+"*2+"+n+"*1");
total++;
}

}
}
}
}

}
System.out.println(total);
}

按此算法总共得结果4562种并列出所有解

lovingpig 2007-03-08