2 git xy git_xy 于 2016.01.13 16:43 提问

c语言算法,基数求解最小构成

功能:有一组基数值(正整数),输入一个正整数(小于100),
问:如果该数由基数值相加构成(每个基数可以重复使用)
,那么最少可能利用的基数是多少个。

 #include  <stdio.h> 
#include  <stdlib.h>   
#define   MAXSiZE   100  
/*#define   min(a,b)  ((a) <= (b) ? (a) : (b))*/   
void  main(void) 
{    
    int  num[MAXSiZE+1];   
    int  base[] = {1,3,4};   
    int  k= sizeof(base)/sizeof(int);
    int  n;    
    int  i, j, MIN;
    scanf("%d",&n);
    num[0] = 0;   
    num[1] = 1;    
    //------------------------1111------------------
    for (i = 2; i <= n; i++)    
    {
        MIN=n;
        for(j=0;j<k;j++)       
            if (i>=base[j])          
                MIN=min(num[i-base[j]]+1,MIN);
        num[i]=MIN;
    }   
    printf("Minimum = %\nd",num[n]);
}

这里使用到了贪心算法了吗?
从 1 位置往下研究了很长时间,还是没看懂,那么大神帮忙讲解一番
谢了

1个回答

devmiao
devmiao   Ds   Rxr 2016.01.14 03:08
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!