硬币问题——记忆化搜索与递推的转换
2023-09-27 14:27:46 时间
一、问题描述
有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 }
这也再一次告诉我们,递归和循环,记忆化搜索和递推可以转化。
记忆化搜索和递推对每个状态值都只计算一次,前者需要递归实现,后者当前状态只与之前状态有关,由于是从最初始的出发,计算当前状态时,保证了之前的状态值已经被求出。
相关文章
- python list 转换为带索引的 字典
- c#代码 天气接口 一分钟搞懂你的博客为什么没人看 看完python这段爬虫代码,java流泪了c#沉默了 图片二进制转换与存入数据库相关 C#7.0--引用返回值和引用局部变量 JS直接调用C#后台方法(ajax调用) Linq To Json SqlServer 递归查询
- C#实现多级子目录Zip压缩解压实例 NET4.6下的UTC时间转换 [译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了 asp.Net Core免费开源分布式异常日志收集框架Exceptionless安装配置以及简单使用图文教程 asp.net core异步进行新增操作并且需要判断某些字段是否重复的三种解决方案 .NET Core开发日志
- 深度 | 探索实物与VR间重量转换的方法
- python中数字和字符串和bytes的相互转换实例解析
- 加密解密基础问题:字节数组和(16进制)字符串的相互转换
- Excel 数据透视表小技巧之 03 将3行转位3列,行列转换基于多重合并计算区域 (教程含数据和解决方案)
- python经常使用的十进制、16进制、字符串、字节串之间的转换(长期更新帖)
- 【leetcode】:109. 有序链表转换二叉搜索树
- CAD图纸版本太高打不开怎么办?CAD版本转换教程
- Java反射机制深入学习(反射 实现配置文件 到 自定义注解转换 案例实现)