硬币问题
有n种硬币，面值分别为V1，V2，...,Vn，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。1<=n<=100, 0<=S<=10000,1<=Vi<=S.
分析：
我们把每种面值看做一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0.若当前在状态 i ，每使用一个硬币j ，状态便转移到 i-Vj .
注意到最长路和最短路的求法是类似的，下面只考虑最长路。由于终点固定，d(i)的确切含义变为“从结点i出发到结点0的最长路径长度”
在记忆化搜索中，如果用特殊值表示“还没算过”，则必须将其和其他特殊值（比如无解）区分开。
也可以不用特殊值表示还没算过，而是用另外一个数组vis[i]表示状态i “是否被访问过”
记忆化搜索代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn = 102, maxv = 10005; 6 int n, S, v[maxn], mind[maxv], maxd[maxv]; 7 int dp1(int s) //最小值 8 { 9 int &ans = mind[s];10 if(ans != -1) return ans;11 ans = 1<<30;12 for(int i = 1; i <= n; ++i) if(v[i] <= s) ans = min(ans, dp1(s-v[i])+1);13 return ans;14 }15 int vis[maxv];16 int dp2(int s) //最大值17 {18 if(vis[s]) return maxd[s];19 vis[s] = 1;20 int &ans = maxd[s];21 ans = -1<<30;22 for(int i = 1; i <= n; ++i) if(s >= v[i]) ans = max(ans, dp2(s-v[i])+1);23 return ans;24 }25 void print_ans(int* d, int s) //打印的是边26 {27 for(int i = 1; i <= n; ++i) if(v[i] <= s && d[s-v[i]]+1 ==d[s])28 {29 printf("%d ",i);30 print_ans(d, s-v[i]);31 break;32 }33 }34 int main()35 {36 freopen("9-3.in", "r", stdin);37 scanf("%d%d", &n, &S);38 for(int i = 1; i <= n; ++i) scanf("%d", v+i);39 memset(mind, -1, sizeof(mind));40 mind[0] = 0;41 printf("%d\n", dp1(S));42 print_ans(mind, S);43 printf("\n");44 memset(maxd, -1, sizeof(maxd));45 memset(vis, 0, sizeof(vis));46 maxd[0] = 0;47 vis[0] = 1;48 printf("%d\n", dp2(S));49 print_ans(maxd, S);50 printf("\n");51 return 0;52 }
递推代码如下：
1 #include2 #include 3 const int maxn = 110, maxv = 10086, INF = 1234567890; 4 int v[maxn], S, n, maxf[maxv], minf[maxv], min_coin[maxv], max_coin[maxv]; 5 void print_ans(int *d, int s){ 6 while(s){ 7 printf("%d ", d[s]); 8 s-=v[d[s]]; 9 }10 } 11 int main(){12 freopen("9-3.in", "r", stdin);13 scanf("%d%d", &n, &S);14 for(int i = 1; i <= n; ++i) scanf("%d", &v[i]);15 for(int i = 1; i <= S; ++i) {16 //最应注意的是边界条件、初始化，因为递推作为重点一般不会写错，就是在这种细节处出错 17 maxf[i] = -INF; 18 minf[i] = INF;19 } 20 maxf[0] = minf[0] = 0;21 for(int i = 1; i <= S; ++i)22 for(int j = 1; j <= n; ++j) if(i >= v[j]){23 if(maxf[i-v[j]] + 1 > maxf[i]){24 maxf[i] = maxf[i-v[j]] + 1;25 max_coin[i] = j;26 }27 if(minf[i-v[j]] + 1 < minf[i]){28 minf[i] = minf[i-v[j]] + 1;29 min_coin[i] = j; 30 }31 }32 printf("%d\n", minf[S]);33 print_ans(min_coin, S);34 printf("\n");35 printf("%d\n", maxf[S]);36 print_ans(max_coin, S);37 printf("\n");38 return 0;39 }
不必打印路径代码：
1 #include2 #include 3 const int maxn = 110, maxv = 10086, INF = 123456789; 4 int n, S, v[maxn], min[maxv], max[maxv]; 5 int main(){ 6 scanf("%d%d", &n, &S); 7 for(int i = 1; i <= n; ++i) scanf("%d", v+i); 8 min[0] = max[0] = 0; 9 for(int i = 1; i <= S; ++i) {min[i] = INF; max[i] = -INF;}10 for(int i = 1; i <= S; ++i)11 for(int j = 1; j <= n; ++j) if(v[j] <= i){12 if(min[i-v[j]] + 1 < min[i]) min[i] = min[i-v[j]] + 1;13 if(max[i-v[j]] + 1 > max[i]) max[i] = max[i-v[j]] + 1;14 }15 printf("%d\n", min[S]);16 printf("%d\n", max[S]);17 return 0;18 }