零钱兑换(Coins Change) -动态规划C语言实现

这篇具有很好参考价值的文章主要介绍了零钱兑换(Coins Change) -动态规划C语言实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

零钱兑换(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(ic1)+1f(ic2)+1...f(ick)+1};(1<=k<=n and i>=ck)
直接引用Leetcode答案的一张递归图来阐述此问题,有三类硬币面额{1,2,3},现在有6的金额总数需要兑换,请问需要的最少硬币个数。

下面的递归树,除了底层的结点,实际上由三叉树组成。对于每个问题,我们都有三个选择,每个选择的代价为1,路径的长度代表了每类选择所需的硬币个数。显而易见的是,如果兑换总额为6,最少所需硬币个数组合为最右边的路径(3+3),所需硬币个数为2;同理,也可以求得最多硬币个数组合为最左边的路径(1+1+1+1+1+1),所需硬币个数为6。

零钱兑换(Coins Change) -动态规划C语言实现

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(ick)+1};(1<=k<=n and i>=ck)ck表示第k个硬币的面额,此问题中我们有n个硬币可供选择
零钱兑换(Coins Change) -动态规划C语言实现

以第二层橙色方框内的节点为例,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)表示相同子问题,两个紫色矩形框内的子问题表示相同的子问题。

零钱兑换(Coins Change) -动态规划C语言实现

零钱兑换问题同时满足最优子结构和重叠子问题两大特征,采用动态规划解决问题是自然而然的选择,也是问题解决的最佳方案。

对于动态规划的子问题,要求子问题互相独立,不能形成环(互相依赖,没有递归出口或迭代的起始),评价子问题是否依赖的有效手段为绘制有向无环图(DAG),以本问题为例,DAG依赖关系为:

零钱兑换(Coins Change) -动态规划C语言实现

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的金额,也无法完成兑换。

对于迭代动态规划,可以从空集∅开始,逐步进行叠加,对于本问题,迭代的过程表示为:

零钱兑换(Coins Change) -动态规划C语言实现

代码实现:

/**
 * @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

  1. https://leetcode.cn/problems/coin-change/description/
  2. 《Introduction to algorithm, 4ed, 4 edition》

到了这里,关于零钱兑换(Coins Change) -动态规划C语言实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 零钱兑换 II(力扣)动态规划 JAVA

    给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 输入:amou

    2024年02月16日
    浏览(42)
  • 零钱兑换 II 力扣(动态规划) JAVA

    给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 输入:amou

    2024年02月15日
    浏览(36)
  • leetcode 动态规划(爬楼梯、零钱兑换、完全平方数)

    卡码网:57. 爬楼梯(opens new window) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 = m n)个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 输入描述:输入共一行,包含两个正整数,分别表示n, m 输出描述:输出一个整数,表

    2024年01月17日
    浏览(40)
  • leetcode动态规划(零钱兑换II、组合总和 Ⅳ)

    给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面

    2024年02月01日
    浏览(41)
  • 动态规划part06 518. 零钱兑换 II 377. 组合总和 Ⅳ

     518 零钱兑换|| 377. 组合总和 Ⅳ  

    2024年01月20日
    浏览(46)
  • LeetCode518. 零钱兑换 II 以及 动态规划相关的排列组合问题

    一、题目 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1: 示

    2024年02月09日
    浏览(42)
  • 【LeetCode动态规划#08】完全背包问题实战与分析(零钱兑换II)

    力扣题目链接(opens new window) 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2: 输入: amount = 3

    2023年04月19日
    浏览(44)
  • Day 44 | 动态规划 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ

    题目 文章讲解 视频讲解 完全背包和0-1背包的区别在于:物品是否可以重复使用 思路:对于完全背包问题,内层循环的遍历方式应该是从weight[i]开始一直遍历到V,而不是从V到weight[i]。这样可以确保每种物品可以被选择多次放入背包,从而求解完全背包问题。 对于完全背包问

    2024年02月20日
    浏览(41)
  • 算法 DAY44 动态规划6 完全背包 518. 零钱兑换 II 377. 组合总和 Ⅳ

    有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件。 动规五步曲来分

    2024年02月01日
    浏览(52)
  • 力扣算法刷题Day44|动态规划:完全背包问题 零钱兑换II 组合总和Ⅳ

    力扣题目:#518.零钱兑换II(完全背包组合问题) 刷题时长:7min 解题方法:动态规划(完全背包) 复杂度分析 时间复杂度: O(mn),其中 m 是amount,n 是 coins 的长度 空间复杂度: O(m) 问题总结 对递推公式的理解 本题收获 题意转换:纯完全背包是凑成背包最大价值是多少,而本

    2024年02月13日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包