硬币问题

[c]代码库

#include <stdio.h>
#include <stdlib.h>

#define INF 100000000
#define MAXNUM 10000
#define MONEYKIND 100

int n,S;
int V[MONEYKIND];
int min[MAXNUM],max[MAXNUM];

void dp(int*,int*);
//递推方法函数声明
void print_ans(int*,int);
//输出函数声明

int main()
{
    int i;
    printf("输入硬币的种数n(1-100):\n");
    scanf("%d",&n);
    printf("输入要组合的钱数S(0-10000):\n");
    scanf("%d",&S);
    printf("输入硬币种类：\n");
    for(i=1; i<=n; i++)
    {
        scanf("%d",&V[i]);
    }
    dp(min,max);
    printf("最小组合方案：\n");
    print_ans(min,S);
    printf("\n");
    printf("最大组合方案：\n");
    print_ans(max,S);

    return 0;
}

void dp(int *min,int *max)
//递推过程实现
{
    int i,j;
    min[0] = max[0] = 0;
    for(i=1; i<=S; i++)//初始化数组
    {
        min[i]=INF;
        max[i]=-INF;
    }
    for(i=1; i<=S; i++)
        for(j=1; j<=n; j++)
            if(i>=V[j])
            {
                if(min[i-V[j]]+1<min[i]){
                    min[i]=min[i-V[j]]+1;//最小组合过程
                    //printf("%d\n",min[i]);
                }
                if(max[i-V[j]]+1>max[i])
                    max[i]=max[i-V[j]]+1;//最大组合过程
            }
}

void print_ans(int *d,int S)
//输出函数实现
{
    int i;
    for(i=1; i<=n; i++)
        if(S>=V[i]&&d[S]==d[S-V[i]]+1)
        {
            printf("%d-",V[i]);
            print_ans(d,S-V[i]);
            break;
        }
}