最少硬币数量-完全背包算法

举报
Linux猿 发表于 2022/02/28 21:51:14 2022/02/28
【摘要】 🎈 作者:Linux猿🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬目录一、题目描述二、测试样例2.1 测试样例一2.2 测试样例二2.3 测试样例三三、算法思路四、代码实现...

🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


目录

一、题目描述

二、测试样例

2.1 测试样例一

2.2 测试样例二

2.3 测试样例三

三、算法思路

四、代码实现

五、复杂度分析

5.1 时间复杂度

5.2 空间复杂度

六、总结


背包算法是经常考查的一类算法,下面来看一道完全背包问题。

一、题目描述

给定一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。

提示:

1 <= coins.length <= 12

1 <= coins[i] <= 2^31 - 1

0 <= amount <= 10^4

二、测试样例

2.1 测试样例一

输入:coins = [1, 2, 5], amount = 11

输出:3

说明:总金额 11 可以由 5 + 5 + 1 组合得到,一共使用了三个硬币。

2.2 测试样例二

输入:coins = [2], amount = 3

输出:-1

说明:在输入中,无论如何 2 都无法得到 3,所以输出 -1。

2.3 测试样例三

输入:coins = [1], amount = 0

输出:0

说明:在输入中,不需要硬币即可得到 0,所以输出 0。

三、算法思路

本题主要考查完全背包算法,可以把硬币看作物品,amount 看作背包容量,本题中的每类物品是无限的,所以是完全背包,但是,本题求解的是最少硬币数,这一点需要特殊处理一下。

使用 dp 数组存储最优解,dp[ i ] 表示背包容量为 i 的时候装满背包需要的最少硬币数,最后的结果即为 dp[ amount ]。

当然,需要注意无法组成 amount 的情况。 

四、代码实现

代码实现如下所示:

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(!amount) return amount;
        int dp[amount + 5];
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i < (int)coins.size(); ++i) {
            for(int j = coins[i]; j <= amount; ++j) {
                if(dp[j-coins[i]] == -1) continue;
                if(dp[j] == -1) {
                    dp[j] = dp[j-coins[i]] + 1;
                } else {
                    dp[j] = min(dp[j], dp[j-coins[i]] + 1);
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }
};

int main()
{
    int a[] = {1, 2, 5};
    vector<int>coins(a, a + 3);

    Solution obj;
    cout<<obj.coinChange(coins, 11)<<endl;
    return 0;
}
图1 通过截图

 

五、复杂度分析

5.1 时间复杂度

时间复杂度为:O(nm),其中,n 为硬币个数,m 为 amount,在上述算法中,使用到了两个 for 循环,长度分别为 n 和 m,所以时间复杂度为 O(nm)。

5.2 空间复杂度

空间复杂度为:O(m),其中,m 为 amount,在上述算法中,使用 dp 数组存储最优解,所以空间复杂度为 O(m)。

六、总结

 本题主要考查对完全背包的理解,同时,也要处理最少硬币数,和完全背包有一些差异。


🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏: 数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200