硬币找零问题,硬币数有限制
问题描述:
有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面值需要的最少张数。
[解决办法]
贪心算法行不啊?老师好像讲过~~