动态规划的应用 急求解答步骤!!!!!!!!!! 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 最小,请给出求解
这个问题的贪婪算法。

看这个图片
展开
 我来答
由浓绮rn
2011-06-12 · 贡献了超过457个回答
知道答主
回答量:457
采纳率:0%
帮助的人:70.8万
展开全部
你也湖工大的吧
追问
你怎么知道的!选修课?
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 1条折叠回答
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式