硬币问题——记忆化搜索与递推的转换

2018/08/08 20:56
阅读数 55

一、问题描述

有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\n");        //此时res1是一个略大于 -INF 的数
50     else printf("%d\n", res1);
51     if (res2 == INF)  printf("impossible\n");
52     else  printf("%d\n", 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\n");        //此时res1是一个略大于 -INF 的数
25     else printf("%d\n", res1);
26     if (res2 == INF)  printf("impossible\n");
27     else  printf("%d\n", res2);
28 }

这也再一次告诉我们,递归和循环,记忆化搜索和递推可以转化。

记忆化搜索和递推对每个状态值都只计算一次,前者需要递归实现,后者当前状态只与之前状态有关,由于是从最初始的出发,计算当前状态时,保证了之前的状态值已经被求出。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部