整币兑零问题？ - 编程论坛

#2

cnfarer2010-07-29 20:48

可以用穷举法

#3

佳嘉2010-07-29 21:51

回复 2楼 cnfarer

恩，但我们现在在学递推，需要用递推来做

#4

2010-08-14 04:14

假设共有 C0 C1 C2 .....Cn中零钱找钱总是为W，f(W)为最优解
那么一定有f(W)=min{f(W-Ci)+1}(Ci<=W且0<=i<=k) 由此可以利用递推求出答案，但是递推太浪费资源，程序会想穷举一样运行时间很长。
我们可以从W=0~W计算出f(w)
首先f(0)=0;
f(Ci）=1；
f(w)=min{f(w-Ci)};
这样运行时间会降低至O（W*k)
这是用动态规划的思想，楼主自己再自己想想，查查资料吧。

#5

佳嘉2010-08-21 20:37

回复 4楼 LegendofMine

谢谢

#6

acman2010-08-24 09:40

DPDPDPDPDPDPDPDP
就是王道

#7

cherryunix2010-09-10 11:27

递推的思路就是，当前节点能不能拓展，如果能拓展就做，不能就退出
这么说应该明白了吧

#8

佳嘉2010-09-10 11:53

回复 7楼 cherryunix

呵呵，早就懂了，不过实现的时候可不是那么简单

#9

cherryunix2010-09-10 12:36

那只能说明你没有真正理解，多做点题吧

#10

vandychan2010-09-10 13:06

典型的贪心

#11

佳嘉2010-09-10 15:00

回复 10楼 vandychan

贪心？？能解决吗？我要的是可行解的总数，而不是最优解

#12

佳嘉2010-09-10 15:04

回复 4楼 LegendofMine

动态规划是可以做，我会，我只是想用不同的方法解决这个问题，穷举，回溯，动态规划这些太常见了

#13

2010-09-12 19:38

回复 12楼佳嘉

呵呵，想想也是哈。我只了解，这个题好像有些时候是不能用贪心算法解的，不过我还没想明白，谁知道回溯怎么解呢？线性规划也能做，最好是大家能多贴贴代码上来。

#14

佳嘉2010-09-12 23:22

回复 13楼 LegendofMine

那我先来一个，这个是我们上课的时候老师给的代码，我自己写的不是很规范，所以就给老师的了
这是用递推做的

#include<stdio.h>
void main()
{
    int p,i,j,m,n,k;
   static int x[12];
  static long int a[12][1001];
  long b,s;
  printf("请输入整币值(单位数):");            /* 输入处理数据 */
  scanf("%d",&m);
  printf("请输入零币种数:");
  scanf("%d",&n);
  printf("(从小至大依次输入每种零币值)\n");
  for(i=1;i<=n;i++)
     {
      printf("第%d种零币值(单位数):",i);
      scanf("%d",&x[i]);
  }
  for(i=0;i<=m;i++)                           /* 确定初始条件 */
      if(i%x[1]==0) a[1][i]=1; else a[1][i]=0;
  for(s=a[1][m],j=2;j<=n;j++)           /* 递推计算a(2,m),a(3,m),...*/
     {
      for(i=x[j];i<=m;i++)
     {
          p=i-x[j];b=0;
         for(k=1;k<=j;k++)
            b+=a[k][p];
            a[j][i]=b;}
            s+=a[j][m];
  }                     /* 累加a(1,m),a(2,m),...*/
  printf("整币兑零种数为:%ld\n",s);           /* 输出兑零种数 */
}