零钱兑换(Coins Change) -动态规划C语言实现
1. 前言
零钱兑换是经典的动态规划问题,也是贪心解法不足的反证答案。它要求兑换一定总整数的零钱,满足硬币数量最少的条件。假定我们有3类零钱,构成数组coins[]={1,7,10},现在兑换总额14的金额,如果采用贪心策略,我们有10+1+1+1+1=14, 共需要5枚硬币。实际上本题的最少硬币方案为7+7=14,仅需要两枚硬币即可。 这实际上就体现了动态规划的优势,try them and try them all.
2. 问题描述
给你一个整数数组
coins
,表示不同面额的硬币;以及一个整数amount
,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回-1
。你可以认为每种硬币的数量是无限的。(https://leetcode.cn/problems/coin-change/description/)
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
3. 问题解决
遵从《算法导论》上的CRCC模式,我们对此问题展开具体的分析,采用递归的思路进行初步问题分析,假定f(i)为总金额为i情况下,最少的硬币个数,同时假定有n个不同的硬币类型。
a) 表征最优问题的结构Characterize the structure of the optimal solution
需要解决的问题是,如何利用f(i)之前的信息,求出f(i)当前的值。利用现有的信息,能确定的变量为金额总数,而且当前的金额为i, 那么就有:
f
(
i
)
=
m
i
n
{
f
(
i
−
c
1
)
+
1
,
f
(
i
−
c
2
)
+
1...
f
(
i
−
c
k
)
+
1
}
;
(
1
<
=
k
<
=
n
a
n
d
i
>
=
c
k
)
f(i)=min\{f(i-c_1)+1,f(i-c_2)+1...f(i-c_k)+1\}; (1<=k<=n\ and\ i>=c_k)
f(i)=min{f(i−c1)+1,f(i−c2)+1...f(i−ck)+1};(1<=k<=n and i>=ck)
直接引用Leetcode答案的一张递归图来阐述此问题,有三类硬币面额{1,2,3},现在有6的金额总数需要兑换,请问需要的最少硬币个数。
下面的递归树,除了底层的结点,实际上由三叉树组成。对于每个问题,我们都有三个选择,每个选择的代价为1,路径的长度代表了每类选择所需的硬币个数。显而易见的是,如果兑换总额为6,最少所需硬币个数组合为最右边的路径(3+3),所需硬币个数为2;同理,也可以求得最多硬币个数组合为最左边的路径(1+1+1+1+1+1),所需硬币个数为6。
b) 递归定义子问题的值(Recursively define the value of the optimal solution)
要达到递归定义子问题的值的目的,一般情况下就需要对第一步的子问题进行抽象处理,形成循环递归的形式,循环递归的本质是构成多叉树,回到问题的本身,由于上面问题的子问题的结构和形式一致,而且对于每个子问题的选择,其代价(附加值)都为1,所以很容易抽象为关系式:
f
(
i
)
=
m
i
n
{
f
(
i
−
c
k
)
+
1
}
;
(
1
<
=
k
<
=
n
a
n
d
i
>
=
c
k
)
c
k
表示第
k
个硬币的面额,此问题中我们有
n
个硬币可供选择
f(i)=min\{f(i-c_k)+1\}; (1<=k<=n\ and\ i>=c_k) \\c_k表示第k个硬币的面额,此问题中我们有n个硬币可供选择
f(i)=min{f(i−ck)+1};(1<=k<=n and i>=ck)ck表示第k个硬币的面额,此问题中我们有n个硬币可供选择
以第二层橙色方框内的节点为例,F(5)=2,F(4)=2,F(3)=1, 那么最终就有计算结果为2,
F
(
6
)
=
m
i
n
{
F
(
5
)
+
1
,
F
(
4
)
+
1
,
F
(
3
)
+
1
}
=
{
3
,
3
,
2
}
=
2
\begin {align} &F(6)\\&=min\{F(5)+1,F(4)+1,F(3)+1\}\\&=\{3,3,2\}\\&=2 \end {align}
F(6)=min{F(5)+1,F(4)+1,F(3)+1}={3,3,2}=2
借此问题,再次回顾动态规划问题的的两大要素,
第一个要素为最优子结构,每个节点都有最优子结构,其最优子结构为三叉树遍历最小值,其它最优子结构一定建立在底层的最优子结构的基础之上的,如果要求F(6)的所需硬币最少个数,那么就需要在F(5)+1,F(4)+1,F(3)+1三个最优子结构当中去寻找。
第二要素为重叠子问题(overlapping subproblem), 对于硬币兑换,重叠子问题显而易见,下图清楚显示子问题的重复。相同颜色和形状的子问题,理解问题重复的子问题,两个橘色矩形框内F(4)表示相同子问题,两个紫色矩形框内的子问题表示相同的子问题。
零钱兑换问题同时满足最优子结构和重叠子问题两大特征,采用动态规划解决问题是自然而然的选择,也是问题解决的最佳方案。
对于动态规划的子问题,要求子问题互相独立,不能形成环(互相依赖,没有递归出口或迭代的起始),评价子问题是否依赖的有效手段为绘制有向无环图(DAG),以本问题为例,DAG依赖关系为:
c) 计算递归定义的值(Compute the value of the optimal solution)
计算递归的核心是定义递归的终止条件,如果没有递归的终止条件,那么递归函数就会出现爆栈的错误,无法获得最终的计算值。针对本问题,我们有两个递归的终止条件:
- 如果要兑换的总金额为0,那么所需最少的硬币个数为0
- 如果要兑换的总金额为负值,那么返回-1,由于递归的原因,如果底层返回为负值,那么就不会对相应的最小值进行更新,而且需要每一层都返回负值,表示没有找到合适的零钱组合
具体计算过程中,我们可以用min_value和函数的返回值进行比较,从而求得最少的硬币个数。同时我们可以设定全局变量value[]数组,对所选择的硬币面额进行保存,方便给出最终的解方案。
d) 构建最优问题的解路径/集合(Construct the solution of the optimal problem)
构建最优问题的解路径/集合,本问题我们用全局变量value[]数组进行追踪。
4. 代码实现
首先采用递归+memoization的方式实现动态规划,递归的出口已在 计算递归定义的值的章节中给出了答案,所以只需要给出memoization数组即可。
a)头文件定义
/**
* @file coins_change.h
* @author your name (you@domain.com)
* @brief https://leetcode.cn/problems/coin-change/description/
* @version 0.1
* @date 2023-03-06
*
* @copyright Copyright (c) 2023
*
*/
#ifndef COINS_CHANGE_H
#define COINS_CHANGE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
int value[10];
int coins_change(int *coins,int n, int rem);
int coins_change_aux(int *coins, int *count, int n, int rem);
#endif
b) 函数实现
/**
* @file coins_change.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-06
*
* @copyright Copyright (c) 2023
*
*/
#ifndef COINS_CHANGE_C
#define COINS_CHANGE_C
#include "coins_change.h"
int coins_change(int *coins, int n, int rem)
{
int *count;
int i;
count=(int *)malloc(sizeof(int)*rem);
for(i=0;i<rem;i++)
{
*(count+i)=INT_MIN;
}
return coins_change_aux(coins,count,n,rem);
}
int coins_change_aux(int *coins, int *count, int n, int rem)
{
int i;
int min_value;
int res;
if(rem<0)
{
return -1;
}
if(rem==0) //if the remaining is zero, then return zero coins
{
return 0;
}
if(count[rem-1]!=INT_MIN)
{
return count[rem-1];
}
min_value=INT_MAX;
for(i=0;i<n;i++)
{
res=coins_change_aux(coins,count,n,rem-coins[i]);
// if res==-1, it won't implement the following actions
if(res>=0 && res<min_value)
{
min_value=res+1; // compare min_value in the different level of tree
value[res]=coins[i];
}
}
//if min_value equals to INT_MAX, then it indicates there is no solution
count[rem-1]=(min_value==INT_MAX?-1:min_value);
return count[rem-1];
}
#endif
c.) 测试函数
/**
* @file coins_change_main.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-03-06
*
* @copyright Copyright (c) 2023
*
*/
#ifndef COINS_CHANGE_MAIN_C
#define COINS_CHANGE_MAIN_C
#include "coins_change.c"
#define N 3
int main(void)
{
int n;
int amount;
int number;
int coins[N]={1,2,5};
n=N;
amount =11;
number=coins_change(coins,n,amount);
printf("The minimum number is %d\n",number);
getchar();
return EXIT_SUCCESS;
}
#endif
如果采用迭代方式,那么就需要定义迭代前的base值,这个base值多数情况表示空集合或最大集合情况下的dp数组值。本例中,我们定义要兑换的总金额为dp数组的维度,dp[amount+1]储存从0到amount条件下的最小硬币个数,显然dp[0]=0,对于其它的DP[1…amount]我们可以默认其维度为最大金额+1,以方便后续比较。
对于最小硬币个数大于总金额的情况,认为其无法提供最终的方案,因为最小硬币的面额为1,对于硬币个数大于总金额,意思是即使用面值为1的金额,也无法完成兑换。
对于迭代动态规划,可以从空集∅开始,逐步进行叠加,对于本问题,迭代的过程表示为:
代码实现:
/**
* @file coins_change.c
* @author your name (you@domain.com)
* @brief Coins change will be implemented by iterative method
* @version 0.1
* @date 2023-03-07
*
* @copyright Copyright (c) 2023
*
*/
#ifndef COINS_CHANGE_C
#define COINS_CHANGE_C
#include "coins_change.h"
int coins_change(int *coins, int **dp, int n, int amount)
{
//major variable will become to 0 in the fast way
//other parameter will not change or change in a slow way
int i;
int j;
*dp=(int *)malloc(sizeof(int)*(amount+1));
for(i=0;i<=amount;i++)
{
(*dp)[i]=amount+1;
}
(*dp)[0]=0;
for(i=1;i<=amount;i++)
{
for(j=0;j<n;j++)
{
if(coins[j]<=i)
{
(*dp)[i]=min((*dp)[i],(*dp)[i-coins[j]]+1);
}
}
}
return ((*dp)[amount]>(amount)?-1:(*dp)[amount]);
}
int min(int m, int n)
{
return (m<n?m:n);
}
#endif
5. 小结
本问题属于经典的动态规划问题,同时满足最优子问题和重叠子树两个条件,而且对于子问题,不存在互相依赖的环(DAG),我们利用递归和迭代两种方式对问题进行实现和编码。文章来源:https://www.toymoban.com/news/detail-487203.html
参考资料:文章来源地址https://www.toymoban.com/news/detail-487203.html
- https://leetcode.cn/problems/coin-change/description/
- 《Introduction to algorithm, 4ed, 4 edition》
到了这里,关于零钱兑换(Coins Change) -动态规划C语言实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!