/*
【问题描述】
有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的一个关系，只不过记忆法不按顺序，而递推是顺序地完成。
