一、问题描述
有n种硬币，面值分别为V1,V2,V3,...,Vn,每种都有无限多。给定非负整数S,可以选用多少硬币，使得面值之和恰好为S?输出硬币数目的最小值和最大值。1≤n≤100,0≤S≤10000,1≤Vi≤S.
二、解题思路
将每种面值看作一个点，表示“还需凑足的面值”，则初始状态为S，目标状态为0。对于状态i,如果存在硬币j,i ≥ Vj,则说可从状态 i 转到
i - Vj，即存在 i--> i-Vj 的有向边。之前矩形嵌套没有固定起点、终点，直接求图上的最长路。这题由于硬币数量无限，图是无限大的，所以必须固定起点和终点（其实就是将图的大小固定）。然后求起点S到终点0的最长路和最短路。
三、代码实现
代码一：对最长路、最短路分别使用dp
1 #include<stdio.h> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 const int maxn = 100 + 10; 9 const int maxs = 10000 + 10; 10 int n,V[maxn]; 11 int dmin[maxs],dmax[maxs]; //d[i]表示从节点i出发到节点0的最长路径的长度 12 int S; 13 14 int dp(int s) 15 { 16 int& ans = dmax[s]; 17 if (ans != -1) return ans; 18 ans = -INF; 19 for (int i = 0; i < n; i++) 20 { 21 if(s >= V[i]) 22 ans = max(ans, dp(s - V[i]) + 1); 23 } 24 return ans; 25 } 26 27 int dp2(int s) 28 { 29 int& ans = dmin[s]; 30 if (ans != -1) return ans; 31 ans = INF; 32 for (int i = 0; i < n; i++) 33 { 34 if (s >= V[i]) 35 ans = min(ans, dp2(s - V[i]) + 1); 36 } 37 return ans; 38 } 39 40 void slove() 41 { 42 memset(dmin, -1, sizeof(dmin)); 43 memset(dmax, -1, sizeof(dmax)); //注意初始化，-1表示未访问 44 dmin[0] = dmax[0] = 0; 45 46 int res1 = 0,res2 = 0; 47 res1 = dp(S); 48 res2 = dp2(S); 49 if (res1 < 0) printf("impossible "); //此时res1是一个略大于 -INF 的数 50 else printf("%d ", res1); 51 if (res2 == INF) printf("impossible "); 52 else printf("%d ", res2); 53 } 54 55 int main() 56 { 57 while (scanf("%d",&n) == 1 && n) 58 { 59 scanf("%d", &S); 60 for (int i = 0; i < n; i++) 61 scanf("%d", &V[i]); 62 slove(); 63 } 64 return 0; 65 }
代码二：使用两次dp有点繁琐，使用递推式，就能够合二为一了。
1 //dmin[i]表示从节点i出发到节点0的最短路径的长度 2 //dmax[i]表示从节点i出发到节点0的最长路径的长度 3 int dmin[maxs], dmax[maxs]; 4 void slove() 5 { 6 for (int i = 1; i <= S; i++) 7 { 8 dmin[i] = INF; 9 dmax[i] = -INF; 10 } 11 dmin[0] = dmax[0] = 0; 12 13 for(int i = 0;i <= S;i++) //注意循环的顺序，由小到大 14 for (int j = 0; j < n; j++) 15 { 16 if (i >= V[j]) 17 { 18 dmin[i] = min(dmin[i], dmin[i - V[j]] + 1); 19 dmax[i] = max(dmax[i], dmax[i- V[j]] + 1); 20 } 21 } 22 23 int res1 = dmax[S], res2 = dmin[S]; 24 if (res1 < 0) printf("impossible "); //此时res1是一个略大于 -INF 的数 25 else printf("%d ", res1); 26 if (res2 == INF) printf("impossible "); 27 else printf("%d ", res2); 28 }
这也再一次告诉我们，递归和循环，记忆化搜索和递推可以转化。
记忆化搜索和递推对每个状态值都只计算一次，前者需要递归实现，后者当前状态只与之前状态有关，由于是从最初始的出发，计算当前状态时，保证了之前的状态值已经被求出。