兑换零钱的一个算法题，求高手
我们知道人民币有1、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。
比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
#include <iostream>
using namespace std;
void count(int n)
{
int sum=0;
int i, j, k, p, q, r, s;
for (i = 0; i <= n/100; i++)
for (j = 0; j <= n/50; j++)
for (k = 0; k <= n/20; k++)
for (p = 0; p <= n/10; p++)
for (q = 0; q <= n/5; q++)
for (r = 0; r <= n; r++)
{
s=100*i + 50*j + 20*k + 10*p + 5*q + r;
if(s == n)
{
if (i+j+k+p+q+r<=100)
{
cout<<"金额100：" << i ;
cout<<" 金额50：" << j ;
cout<<" 金额20：" << k ;
cout<<" 金额10：" << p ;
cout<<" 金额5：" << q ;
cout<<" 金额1：" << r << endl; ;
sum++;
}
}
}
cout<<"共有"<<sum<<"种方法！"<<endl;
}
int main()
{
int n;
cin >> n;
while (n != 0)
{
count(n);
cin >> n;
}
system("pause");
return 0;
}
这个是我的解法，大家有没有更好的解法啊？递归，贪心算法？求指导
[解决办法]
回溯
// chuangxingongchan.cpp : 定义控制台应用程序的入口点。
//
#include <vector>
#include <iostream>
#define N = 6
using namespace std;
int count=0;
int Target=0;
int coin[N]={1,5,10,20,50,100};
int total=0;
vector<int> solution;
void dfs(int index)
{
if( total == Target && count<=100 )
{
count++;
cout << count <<":" ;
for( int i=0; i<(int)solution.size(); i++)
{
cout << solution[i]<<" ";
}
cout << endl;
return;
}
if( total > Target
[解决办法]
count >100 )
return;
for( int i=index; i<N; i++)
{
total += coin[i];
solution.push_back( coin[i] );
dfs(i);
solution.pop_back();
total -=coin[i];
}
}
int _tmain(int argc, _TCHAR* argv[])
{
while(1)
{
count=0;
cin >> Target;
dfs(0);
cout << count <<endl;
}
return 0;
}
[解决办法]
你是搞OI的吗？
表示对楼上的做法无解
这道题显然动规
//分析+关键代码
//1、5、10、20、50、100
//由1≤n≤250最先想到的是打表 这是万不得已的方法
//如果你不知道动规 建议最好先去学一下
//用f(i,j)表示 i元 用前(j+1)种 拆分的方法
//有f(i,0)=1 【用1元 组合成i元】
//f(i,j)=sum{f(i-k*coin[j],j-1)};
//动规+记忆化#include<iostream>
using namespace std;
int coin[]={1,5,10,20,50,100};//第一个是1就行 后面顺序任意 否则 需要小改f(int,int)
int ans[260][10]={0};
bool vis[260][10]={0};
int f(int i,int j)
{
if(j==0)return 1;
if(vis[i][j]==true)return ans[i][j];
int k;
for(k=0;k*coin[j]<=i;k++)
ans[i][j]+=f(i-k*coin[j],j-1);
vis[i][j]=true;
return ans[i][j];
}
int main()
{
int n;
cin>>n;
cout<<f(n,5)<<endl;
return 0;
}
[解决办法]
仅供参考
//问题是这样，有N个数字，数值不同，要列出用他们不同的组合相加等于1000的情况。
//比如，a[3]={200,300,400}
//则有的情况为：
//5 0 0
//3 0 1
//2 2 0
//1 0 2
//0 2 1
//等情况。
#include <stdio.h>
int a[3]={200,300,400};
int temp[3]={0,0,0};
void function(int sum, int index) {
int j,i;
if (sum==1000) {
for (j=0;j<3;j++) printf("%d ",temp[j]);
printf("\n");
return;
} else if (sum>1000) return;
else for (i=index;i<3;i++) {
temp[i]++;
function(sum+a[i],i);
temp[i]--;
}
}
void main() {
function(0,0);
}
//5 0 0
//3 0 1
//2 2 0
//1 0 2
//0 2 1
//
[解决办法]
//我们知道人民币有1、5、10、20、50、100这几种面值。
//现在给你n(1≤n≤250)元，让你计算换成用上面这些面额表示且总数不超过100张，共有几种。
//比如4元，能用4张1元、2张1元和1张2元、2张2元，三种表示方法。
#include <stdio.h>
int a[6]={1,5,10,20,50,100};
int temp[6]={0,0,0,0,0,0};
int n,j,k,z;
void function(int sum, int index) {
int i;
if (sum==n) {
k=0;
for (j=0;j<6;j++) k+=temp[j];
if (k>100) return;
z++;
printf("%08d: ",z);
for (j=0;j<6;j++) printf("%d ",temp[j]);
printf("\n");
return;
} else if (sum>n) return;
else for (i=index;i<6;i++) {
temp[i]++;
function(sum+a[i],i);
temp[i]--;
}
}
void main() {
n=250;
z=0;
function(0,0);
}
//00000001: 95 1 1 2 0 1
//00000002: 95 1 0 0 3 0
//00000003: 95 1 0 0 1 1
//00000004: 90 8 0 1 0 1
//00000005: 90 6 3 0 0 1
//...
//00005790: 0 0 0 10 1 0
//00005791: 0 0 0 5 3 0
//00005792: 0 0 0 5 1 1
//00005793: 0 0 0 0 5 0
//00005794: 0 0 0 0 3 1
//00005795: 0 0 0 0 1 2