C语言关于贪心算法的（很简单）

LZ在开始研究ACM嘛？

#include

int

least_num_cash(int

_money)

{

/*直接贪心，能用大张的钞票尽量用大张的*/

int

ret=0

while(_money!=0)

{

if(_money>=100)

{

_money-=100

}

else

if(_money>=50)

{

_money-=50

}

else

if(_money>=20)

{

_money-=20

}

else

if(_money>=10)

{

_money-=10

}

else

if(_money>=5)

{

_money-=5

}

else

if(_money>=2)

{

_money-=2

}

else

if(_money>=1)

{

_money-=1

}

ret++

}

return

ret

}

int

main()

{

int

n,m

while(scanf("%d%d",&n,&m)!=EOF)

{

printf("%d\n",least_num_cash(m-n))

}

return

0

}

贪心算法找零就是现实中从最大面额开始找的思路。不代表是最优解，只是算法之一。

由于面额输入顺序不定，我先对输入的面额进行降序排序。

下面代码：

#include <stdio.h>

#include <malloc.h>

int main()

{

  int i,j,m,n,*ns=NULL,*cn=NULL,sum=0

  printf("请输入总金额m及零钱种类n："),scanf("%d",&m),scanf("%d",&n)

  printf("请分别输入%d种零钱的面额：\n",n)

  if(!(ns=(int *)malloc(sizeof(int)*n))) return 1

  if(!(cn=(int *)malloc(sizeof(int)*n))) return 1

  for(i=0i<ni++) scanf("%d",&ns[i])

  //------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除）

  for(i=0i<ni++)

      for(j=i+1j<nj++)

          if(ns[j]>ns[i]) ns[j]^=ns[i],ns[i]^=ns[j],ns[j]^=ns[i]

  //-------------------------------------------------------------------

  for(i=0i<ni++)//贪心算法，从最大面额开始

      if(m>=ns[i])

          cn[i]=m/ns[i],m=m%ns[i],sum+=cn[i],printf("%d元%d张 ",ns[i],cn[i])

  printf("\n最少使用零钱%d张\n",sum)

  return 0

}

思路：对于一个整数n，无论分成多少个数的和，都是这些数相同或相差最少的时候，它们的积才最大。如，对于数 4, 2 * 2最大；对于9，分成三个数3 * 3 * 3最大，分成两个数4 * 5最大。。。数学里可以证明。

然后分治法就行了

1,2,3这三个数不可分，本身最大，遇到它们直接返回就行了，其它数分完递归调用。

---