[求助]求一个程序的算法
现有面值100，50，20，10，5，1元的纸币足够多，输入一个金额m以及纸币张数n，要求从上述的纸币中找出n张，其总金额正好是m，列出所有的方法。如：输入：120元，3张；输出：1张100、2张10，或2张50、1张20。
----------------解决方案--------------------------------------------------------
你得先保证你 1,输入的数可以用你给出的 现有的面值表示.
2,是不是只能每种面值只能用一次?
----------------解决方案--------------------------------------------------------
既然说了
[QUOTE]
纸币足够多
[/QUOTE]应该可以使用多次。。
#include <stdio.h>
int use[6],num[6]={100,50,20,10,5,1},l_num=6,method,all_used;
void show()
{
int i;
method++;
for (i=0;i<6;i++)
{
if (i) printf(", ");
printf("%d元的%3d张",num[i],use[i]);
}
printf(".\n");
}
void dfs(int need,int deep,int used)
{
int i;
if (deep==6&&need==0&&used==all_used)
{
show();
return ;
}
else if (deep==6) return ;
for (i=0;i*num[deep]<=need && i+used<=all_used;i++)
{
use[deep]=i;
dfs(need-i*num[deep],deep+1,used+i);
}
}
int main()
{
int aim;
while (scanf("%d %d",&aim,&all_used)&&aim)
{
method=0;
dfs(aim,0,0);//需要aim，已经有0,已经使用0张
if (!method) printf("Impossible\n");
}
return 0;
}
int use[6],num[6]={100,50,20,10,5,1},l_num=6,method,all_used;
void show()
{
int i;
method++;
for (i=0;i<6;i++)
{
if (i) printf(", ");
printf("%d元的%3d张",num[i],use[i]);
}
printf(".\n");
}
void dfs(int need,int deep,int used)
{
int i;
if (deep==6&&need==0&&used==all_used)
{
show();
return ;
}
else if (deep==6) return ;
for (i=0;i*num[deep]<=need && i+used<=all_used;i++)
{
use[deep]=i;
dfs(need-i*num[deep],deep+1,used+i);
}
}
int main()
{
int aim;
while (scanf("%d %d",&aim,&all_used)&&aim)
{
method=0;
dfs(aim,0,0);//需要aim，已经有0,已经使用0张
if (!method) printf("Impossible\n");
}
return 0;
}
输入0 X将结束程序
原来还有20的...已改正
[此贴子已经被作者于2007-3-21 13:43:56编辑过]
----------------解决方案--------------------------------------------------------
我想基本思路应该是双重循环吧。
不是很难的，希望楼主自己能多想想 。
呵。。。
----------------解决方案--------------------------------------------------------
OK!!~
写在那里了，小的数据应该没有问题
----------------解决方案--------------------------------------------------------
呵
不错嘛 。。。
要是有错误就好了
呵呵。。。。。。。
----------------解决方案--------------------------------------------------------
非常感谢你们!!!!!!!
----------------解决方案--------------------------------------------------------