要将五张100元的大钞票，换成等值的50元，20元，10元，5元一张的小钞票，要求换成30张小钞票，每种面值的至少一张，编程输出所有可能的换法，程序应适当考虑减少重复次数。
有高手 指点下吗？   循环次数 少于3000次~

等待……

看上去是贪心…………
期待2楼解答

我咋想都不止3000次，一共一万多次，可能的换法有877种，供楼主参考：


// lian.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>

int main(int argc, char* argv[])
{
    long loopCon=0;
    long seccussCon=0;
   
   for(int x=1;x<=7;x++){
       for(int y=1;y<=22;y++){
           for(int z=1;z<=27;z++){
               for(int a=2;a<=27;a++){
                   loopCon++;
                   if(50*x+20*y+10*z+5*a==500){
                       printf("50的%d张，20的%d张，10的%d张，5元的%d张。\n",x,y,z,a);
                       seccussCon++;}
               }
               
           }
       }
   }
   printf("一共进行了%d次循环\n",loopCon);
   printf("可用的循环次数：%d \n",seccussCon);
  getchar();
    return 0;
}

贪心法只能解出一个所谓的最优解。
貌似回溯法解出的也不会超过3000次循环。

如果你再判断循环的条件，发现就没有这么多了。

每种面值的至少一张 要求换成30张小钞票
x+y+z+a=30吗

#include<stdio.h>
void main()
{
int i,j,k,l,n=0,x=0;
for(i=1;i<8;i++)
for(j=1;j<21;j++)
for(k=22;k>0;k=k-3)
{    
l=(500-i*50-j*20-k*10)/5;
if(l>=1)
{    
if(i+j+k+l==30)
{
printf("%d %d %d %d \n",i,j,k,l);
n++;
}                            
}
x++;
}
printf("%d",x);
printf("total=%d",n);        
}
这个程序可行否？

还要加上个
&&x+y+Z+a==30

LS算出了37个解，但是以下程序算出了48个解……

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    int i, j , k, c = 0;
    for (i = 0; i < 10; i++)
        for (j = 0; j < 25; j++)
            for (k = 0; k < 50; k++)
            {
                int l = 500 - 50 * i - 20 * j - 10 * k;
                if (l >= 0 && l % 5 == 0)
                {
                    l /= 5;
                    if (i + j + k + l == 30)
                    {
                        printf("%d %d %d %d\n", i, j, k, l);
                        c++;
                    }
                }
            }
    printf("count:%d\n", c);
    return 0;
}