动态规划的应用 急求解答步骤!!!!!!!!!! 5
动态规划的应用【题目描述】考虑金钱兑现问题。有一个货币系统,它有n种硬币,它们的面值为v1,v2,...,vn,其中v1=1。我们想这样来兑换价值为y的钱,要让硬币的数目...
动态规划的应用
【题目描述】
考虑金钱兑现问题。有一个货币系统,它有 n 种硬币,它们的面值为v1,v2,...,vn,其中
v1 = 1。我们想这样来兑换价值为y 的钱,要让硬币的数目最少。更形式地,我们要让下面
的量
1
n
i
i
x
= Σ
在约束条件
1
n
i i
i
xv y
=
Σ =
下极小。其中,x1,x2,...,xn 是非负整数(xi 可能是0)。
(1)设计求解这个问题的动态规划算法;
(2)你的算法的时间和空间复杂度是多少。
第二题
【知识点】
贪婪算法的应用
【题目描述】
考虑关于钱币兑换的问题,这个问题已在第一题中说明。考虑一个现行的辅币系统,它有以
下面值的硬币:1 元(100 分)、2 角5 分(25 分)、1 角(10 分)、5 分和1 分(单位值的硬
币是永远需要的)。假如要进行币值为n 分的兑换,并让硬币的总个数m 最小,请给出求解
这个问题的贪婪算法。
提
看这个图片 展开
【题目描述】
考虑金钱兑现问题。有一个货币系统,它有 n 种硬币,它们的面值为v1,v2,...,vn,其中
v1 = 1。我们想这样来兑换价值为y 的钱,要让硬币的数目最少。更形式地,我们要让下面
的量
1
n
i
i
x
= Σ
在约束条件
1
n
i i
i
xv y
=
Σ =
下极小。其中,x1,x2,...,xn 是非负整数(xi 可能是0)。
(1)设计求解这个问题的动态规划算法;
(2)你的算法的时间和空间复杂度是多少。
第二题
【知识点】
贪婪算法的应用
【题目描述】
考虑关于钱币兑换的问题,这个问题已在第一题中说明。考虑一个现行的辅币系统,它有以
下面值的硬币:1 元(100 分)、2 角5 分(25 分)、1 角(10 分)、5 分和1 分(单位值的硬
币是永远需要的)。假如要进行币值为n 分的兑换,并让硬币的总个数m 最小,请给出求解
这个问题的贪婪算法。
提
看这个图片 展开
1个回答
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询