功能:有一组基数值(正整数),输入一个正整数(小于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 位置往下研究了很长时间,还是没看懂,那么大神帮忙讲解一番
谢了