DAG模型--硬币问题

/*
【问题描述】
有n种硬币，面值分别为V1，V2，V3，.....Vn，每种都有无限多。
给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？
输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.

【分析与思路】
思路：本题是固定终点和起点的DAG动态规划。
我们把每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0。
如当前在状态i，没使用一个硬币j，状态变转移到i-Vj。
有n种硬币，面值分别为V1，V2，V3，.....Vn，每种都有无限多。
给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？
输出硬币数目的最小值和最大值。1<=n>=100, 0<=S<=10000,1<=Vi<=S.

本题是固定终点和起点的DAG动态规划。
我们把每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0。
如当前在状态i，没使用一个硬币j，状态变转移到i-Vj。
*/

记忆版：

#include<cstdio>  
#include<cstring>  
int d[1000],v[10];  

int cnt=0;
int max(int a, int b)  
{  
    return a > b ? a : b;  
}  
int dpmax(int s,int n)  
{  
    if (d[s] != -1)  
        return d[s];  
        printf("%d ", ++cnt );
    d[s] = -10000;//用于设定不能走到终点的路肯定小于能走到终点的路  
    for (int i = 0;i < n;i++)  
        if (s >= v[i])//等号很关键  
            d[s] = max(d[s], dpmax(s - v[i], n)+1);  
    return d[s];  
}  
  
int main()  
{  
    int n, s, i;  
    while (scanf("%d%d", &n, &s) != EOF)  
    {  
        for (i = 0;i < n;i++)  
            scanf("%d", &v[i]);  
        memset(d, -1, sizeof d);  
        d[0] = 0;//用于辨别该路能否走到终点  
        printf("%d\n", dpmax(s, n));  
    }  
    return 0;  
} 

递推版：

#include<stdio.h>  
#include<string.h>  
#define MAX 10001  
#define INF  1000000000;  
int n, S;  
int V[MAX] ,vis[MAX], d[MAX];  
int max[MAX], min[MAX] ;  
  
// 输出最小字典序  
void prit_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 ", i);  
            prit_ans(d, S-V[i]) ;  
            break ;  
        }  
}  
  
// 主函数、递推实现最短路最长路  
int main ()  
{  
    memset(min,0,sizeof(min));  
    memset(max,0,sizeof(max));  
    memset(V,0,sizeof(V));  
    int i ,j ;  
    min[0] = max[0] = 0;  
    printf("请输入要组成的面值之和S：");  
    scanf("%d", &S) ;  
    printf("请输入不同面值的硬币的种类：");  
    scanf("%d", &n) ;  
    printf("请输入各个种类的硬币的面值：\n");  
    for (i=1; i<=n; i++)  
    {  
        scanf("%d", &V[i]);  
    }  
    // 递推算法求解最长最短路  
    for (i=1; i<=S; i++)///初始化min初始化为最大值，max初始化为最小值  
    {  
        min[i] = INF;  
        max[i] = -INF;  
    }  
    for (i=1; i <= S; i++)///表示的钱数  
        for (j=1; j<=n; j++)///对应的个数  
            if(i >= V[j])///当需要表示的钱币数大于硬币所能表示的数值时，才可以往下进行  
            {  
                ///对min和max进行更新  
                if (min[i] >= (min[i-V[j]] +1))  
                    min[i] = min[i-V[j]] +1;  
                if (max[i] <= (max[i-V[j]] +1))  
                    max[i] = max[i-V[j]] +1;  
            }  
    printf("%d %d\n", min[S], max[S]);  
    //  输出最优字典序  
    prit_ans(min, S);  
    printf("\n");  
    prit_ans(max, S) ;  
    printf("\n");  
  
    return 0 ;  
}  

其实这题就是从1推到s的一个关系，只不过记忆法不按顺序，而递推是顺序地完成。