动态规划,注意不要有重复的,例如组成1角钱,5 2 2 1 和 1 2 2 5是1种组合
算法的设计思想在程序中注释的很清楚。
解法一:
// 动态规划
// total_money: 要找的零钱总和
// changes: 零钱数组,已经从小到大排序,第1个元素设为0,有效元素从第2个位置即下标1开始
// kinds_change: 零钱种类
int make_change_problem(int total_money, int *changes, int kinds_change)
{
// opt[i][j]表示用前j种零钱组成i元钱的组合数目,第j种零钱的数目可以为0
boost::multi_array<int, 2> opt(boost::extents[total_money+1......
阅读全文