金钱兑换问题
(a)在该题中, 种硬币 ,其中 ,用 表示面额为 的钱最少所需要的硬币数目, ,而在本题中,我们要求的就是 的值.
状态转移方程: ,这里初始化时,设置 ,意为每次给的钱均全部使用 来兑换.
伪代码:
Input : n种硬币集合 ,要进行计算的面额
Output : 最少需要的硬币数
For each
End-for
For each
For each
If
End-if
End-for
End-for
Return
(b) 时间复杂度 ,空间复杂度
(c) 这两个算法都同属于优化问题,背包问题在满足背包容量的前提下,来求得最大价值总量;该硬件兑换问题是在满足给定钱的条件下所需要的最少硬币数. 二者都是在满足约束的前提下,对目标进行优化.
2021-09-11 17:29:08
457KB
算法
硬币兑换
1