给定面值为{d1, d2,…, da}的n种硬币,各种硬币数目均充分多.现需要兑换金额N(金额N,面值种数n和硬币面值di(1)均为正整数)。
(1)假设硬币的面值为:{1,2,22,...2n-1}。请设计一个高效的算法计算最少使用多少硬币可以完成兑换(请注意必须严格、详细地论证你的算法的正确性。)(4分)
（2）请设计一个动态规划算法,针对任意给定的硬币面值,计算最少使用多少个硬币可以完成兑换,或者判定无法完成兑换。(8分)
查看答案和解析【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE小班面授 名额有限 抢先体验
为你推荐
编辑推荐
最新内容
姓名
手机号
