首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

硬币找零有关问题,硬币数有限制

2012-04-20 
硬币找零问题,硬币数有限制问题描述:有10元零钱、5元零钱、2元零钱、1元零钱若干张(每种零钱有张数限制),给定

硬币找零问题,硬币数有限制
问题描述:
有10元零钱、5元零钱、2元零钱、1元零钱若干张(每种零钱有张数限制),
给定一个值即需要找的零钱数(小于等于10),找出零钱张数最少的找法

例子:
10元的1张,5元的1张,2元的5张,1元的0张,
需要找的零钱为6元,则方案为:3张2元的

求算法

[解决办法]
就是10块钱可以用0-n1张,5块钱可以用0-n2张,1块钱可以用0-n3张,动态规划或者递归都行,

dp[total][i]表示用i...k这几种纸币凑total面值需要的最少张数。
[解决办法]
贪心算法行不啊?老师好像讲过~~

热点排行