动态规划算法解决找零问题

jsgj2023

现存在一堆面值为V1,V2,V3......个单位的硬币,问最少需要多少个硬币才能找出总值为T个单位的零钱
(假设这一堆硬币的面值分别为1,2,5,21,25元,需要找出总值为63元的零钱)?

qingc0221

香川群子

一共有486个组合解。

其中最简单的解：=3*21=63

5种币值都有的组合：
+1*25+1*21+2*5+3*2+1*1
+1*25+1*21+2*5+2*2+3*1
+1*25+1*21+2*5+1*2+5*1
+1*25+1*21+1*5+5*2+2*1
+1*25+1*21+1*5+4*2+4*1
+1*25+1*21+1*5+3*2+6*1
+1*25+1*21+1*5+2*2+8*1
+1*25+1*21+1*5+1*2+10*1

香川群子

本题目是求【多元一次方程】的整数解。

可以用递归算法求所有组合解。

qingc0221

香川群子 发表于 2017-5-15 21:01
本题目是求【多元一次方程】的整数解。

可以用递归算法求所有组合解。

找零肯定先找大面额的啊XD

凌空一羽

香川群子 发表于 2017-5-15 21:00
一共有486个组合解。

其中最简单的解：=3*21=63

香川女侠，你能不能写这个代码出来啊，递归还不太会，正在翻你的主题看着中……
谢谢

jsgj2023

香川群子 发表于 2017-5-15 21:00
一共有486个组合解。

其中最简单的解：=3*21=63

老师能否给出代码呢?

micch

翻老帖，有哪位老师知道论坛动态规划方面的帖子推荐一下。我看了竞赛版的动态规划那个题，理解起来有点难，想多看一些帖子学习一下