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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
基数估计算法(一):Flajolet-Martin算法
写作不易,转载请注明出处: http://blog.csdn.net/wbin233/article/details/78730977 简介说起基数估计算法的始祖,或许就是由Flajolet和Martin大佬发表的论文《 Probabilistic counting algorithms for data base applications 》开始的吧。他们提出在大数据中基于概率来估计基数的算法,江湖人称FM算法。
递归求最大最小值算法 分治策略(c语言实现)
思路:运用分治的思想,将要排序的整个数组从中间劈开,分别求其左右两边的最大最小值,然后将求出的最大最小值合起来进行比较。     当左右两边的数组小到一定程度时:(1)数组中只有一个元素,maxNum=minNum; ·     (2)数组中有两个元素,找出两个元素中的最大最小值;     (3)数组中大于两个元素,从中间分开,继续递归; #include #include #includ
算法课-分治法求最大最小元
#include&amp;lt;iostream&amp;gt; #include&amp;lt;cstdio&amp;gt; using namespace std; const int maxn=1000; const int inf=0x7f7f7f7f; int a[maxn]; //分治法 求最大元最小元 void Min_Max(int l,int r,int &amp;amp;maxNum,int &amp;amp;minNum...
基数排序C语言代码实现
#include typedef struct { int num; int next; }slcell; //静态链表的结点类型 #define M 11 int f[M]; int e[M]; int head=0; void distribute(slcell *a,int w) { int i; int last; for(i=0;i<10;i++)
基数排序及C语言实现
基数排序及C语言实现
最短哈密顿回路算法C语言实现
最短哈密顿回路,在无向图中由一个顶点出发,不重复的遍历所有顶点,最后回到出发点,找到最短的回路,用C语言实现,
基数排序单链表实现(C语言)
头文件: /*基数排序,单链表实现*/ #ifndef RADIX_SORT_H #define RADIX_SORT_H #include #define FLOWOVER -1 #define LIST_EMPTY -2 struct RadixSort; typedef struct RadixSort * List; typedef struct RadixSort * Node;
最大流/最小割算法总结
1。基本定理:最小割集的流量之和=网络中的最大流。2。求最大流和求最小割集是两类不同的算法。3。解决最大流问题的常用到Ford-Fulkerson方法,之所以称其方法而不是算法,是因为在这种思想下包含着若干种时间复杂度不同的实现,其中较多地是使用Edmonds-Karp算法。与此相对,Push-relabel算法采用了与Ford-Fulkerson方法完全不同的思考角度,降低了渐进意义下的时间复杂度。而relabel-to-front算法则是对Push-relabel算法的改良和精炼,效率更佳。关于这三种常
一般线性规划求最小值+c语言
求最小值的线性规划,任然需要旋转算法。 对于如下的线性函数,求最优解:
回溯法算法思想解决最小机器重量设计问题
开门见山 简单理解回溯法 最小机器重量问题处理 一、回溯法 1.基本概念:     (1)回溯法     回溯算法是一种选优搜索法,按选优条件向前搜索,以达到目标。简单的说是在搜索过程中寻找问题的解,当发现已不满足求解条件时,就回溯返回,尝试别的路径。     当探索到某一步时,发现原先选择不是目前的最优解或不满足问题条件时,就退回一步重新选择,并减去当前步骤的节点对应的值,这种