【每日算法Day 109】五大解法,带你深入了解完全背包方案数

简介: 【每日算法Day 109】五大解法,带你深入了解完全背包方案数

今天这题是完全背包问题 + 背包问题方案数,我一共列举了 5 种解法,层层递进优化。并且从两个角度殊途同归,最终优化到同一个式子。强烈建议掌握,对理解背包问题有很大帮助。

题目链接

LeetCode 面试题 08.11. 硬币[1]

题目描述

给定数量不限的硬币,币值为 25 分、10 分、5 分和 1 分,编写代码计算 n 分有几种表示法。(结果可能会很大,你需要将结果模上 1000000007)

说明:

  • 0 <= n (总金额) <= 1000000

示例1

输入:
n = 5
输出:
2
解释:
有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2

输入:
n = 10
输出:
4
解释:
有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

题解

首先我们规定一些记号,用  来表示第  种硬币的面值,用  表示用前  种硬币组成面值  的方案数。令  表示需要表示的面值, 表示硬币数。

朴素想法(错误)

首先我们可以想到,最朴素的方法不就是组成面值  的方案数等于所有组成面值  的方案数之和

但是这样有个很严重的问题,就是会产生重复计算,也就是将 6 = 1 + 56 = 5 + 1 视为两种情况。

动态规划 1

朴素想法的纠正方法就是,规定拆解后的数字是有序的,这样就不会出现重复计算了。

那么具体怎么实现呢?其实只需要加上一个约束,也就是强制令  为组成面值  的最大面值硬币。那么用掉它之后,组成面值  的最大面值硬币仍然只能是  ,这样转移下去就一定是有序的,不会出现面值突然增大的情况。转移方程只需要修改一下转移后的可用硬币 :

时间复杂度  ,空间复杂度  。

动态规划 2(超时)

另一条思考路线是,我们假设第  个硬币用  枚,然后枚举所有的 就行了。转移方程很好写:

但是这样时间复杂度太高了,直接超时。

时间复杂度  ,空间复杂度  。

转移方程优化

神奇的地方来了,上面两种方法,全部可以优化为同一个式子,仔细看好了。

动态规划 1:

首先看第一个方法,转移方程为:

我们令  ,又可以得到:

两式左右两边相减可以得到:

动态规划 2:

再看第二个方法,转移方程为:

令  ,又可以得到:

两式左右两边相减可以得到:

最终形式:

所以,最终**两个方法消去求和之后,形式是一样的!**都是:

时间复杂度  ,空间复杂度  。

空间优化

注意到,上面转移方程每个时刻  其实只和  还有  时刻有关,所以可以把第一个维度消除掉。这样转移方程就变为了:

但是需要特别注意的是,这里一共有三项,分别表示的是第  时刻、第  时刻、第  时刻。所以在两层循环遍历的时候,第一层循环必须是遍历硬币  ,第二层才是遍历组成的面值  ,这样才不会导致第  时刻的值被覆盖掉无法访问。

时间复杂度  ,空间复杂度  。

数学法

这个方法就只针对本题硬币种类比较少的情况了。

假设组成面值  需要  枚 25 分,  枚 10 分,  枚 5 分,  枚 1 分,那么有:

这里  我们是需要枚举的,范围是  ,所以我们令 ,那么就得到了:

那么  的范围是  。而  确定了之后,  的范围就是  。而  都确定了之后,  是唯一确定了的。所以最终的方案数就是:

所以最终我们遍历 ,然后令 。接着令 ,,最后对  进行累加就行了:

时间复杂度  ,空间复杂度  。

代码

动态规划 1(c++)

class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;
    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};
    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; k <= i; ++k) {
                    if (j >= p[k]) {
                        (dp[i][j] += dp[k][j-p[k]]) %= mod;
                    }
                }
            }
        }
        return dp[M-1][n];
    }
};

动态规划 2(超时)(c++)

class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;
    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};
    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i <= n/p[0]; ++i) dp[0][i*p[0]] = 1;
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int k = 0; k <= j/p[i]; ++k) {
                    (dp[i][j] += dp[i-1][j-k*p[i]]) %= mod;
                }
            }
        }
        return dp[M-1][n];
    }
};

转移方程优化(c++)

class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;
    ll dp[M][N];
    int p[M] = {1, 5, 10, 25};
    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        for (int i = 0; i < M; ++i) dp[i][0] = 1;
        for (int i = 0; i <= n/p[0]; ++i) dp[0][i*p[0]] = 1;
        for (int i = 1; i < M; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j >= p[i]) (dp[i][j] += dp[i][j-p[i]]) %= mod;
            }
        }
        return dp[M-1][n];
    }
};
空间优化(c++)
class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    static const int N = 1000010;
    static const int M = 4;
    ll dp[N];
    int p[M] = {1, 5, 10, 25};
    int waysToChange(int n) {
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int j = 0; j < M; ++j) {
            for (int i = 1; i <= n; ++i) {
                if (i >= p[j]) {
                    (dp[i] += dp[i-p[j]]) %= mod;
                }
            }
        }
        return dp[n];
    }
};

数学法(c++)

class Solution {
public:
    typedef long long ll;
    static const ll mod = 1e9 + 7;
    int waysToChange(int n) {
        ll res = 0;
        for (int i = 0; i <= n/25; ++i) {
            ll r = n - 25 * i;
            ll x = r / 10, y = r / 5;
            (res += (x + 1) * (y - x + 1)) %= mod;
        }
        return res;
    }
};
相关文章
|
8月前
|
传感器 人工智能 监控
智慧工地 AI 算法方案
智慧工地AI算法方案通过集成多种AI算法,实现对工地现场的全方位安全监控、精准质量检测和智能进度管理。该方案涵盖平台层、展现层与应用层、基础层,利用AI技术提升工地管理的效率和安全性,减少人工巡检成本,提高施工质量和进度管理的准确性。方案具备算法精准高效、系统集成度高、可扩展性强和成本效益显著等优势,适用于人员安全管理、施工质量监控和施工进度管理等多个场景。
319 0
|
1月前
|
自然语言处理 算法 数据可视化
文本聚类效果差?5种主流算法性能测试帮你找到最佳方案
本文探讨了自然语言处理中句子嵌入的聚类技术,使用Billingsmoore数据集(925个英语句子)进行实验。通过生成句子嵌入向量并可视化分析,对比了K-Means、DBSCAN、HDBSCAN、凝聚型层次聚类和谱聚类等算法的表现。结果表明,K-Means适合已知聚类数量的场景,DBSCAN和HDBSCAN适用于未知聚类数量且存在异常值的情况,而谱聚类在句子嵌入领域表现不佳。最终建议根据数据特征和计算资源选择合适的算法以实现高质量聚类。
59 0
文本聚类效果差?5种主流算法性能测试帮你找到最佳方案
|
2月前
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
71 7
|
1月前
|
机器学习/深度学习 监控 算法
局域网行为监控软件 C# 多线程数据包捕获算法:基于 KMP 模式匹配的内容分析优化方案探索
本文探讨了一种结合KMP算法的多线程数据包捕获与分析方案,用于局域网行为监控。通过C#实现,该系统可高效检测敏感内容、管理URL访问、分析协议及审计日志。实验表明,相较于传统算法,KMP在处理大规模网络流量时效率显著提升。未来可在算法优化、多模式匹配及机器学习等领域进一步研究。
43 0
|
8月前
|
传感器 人工智能 监控
智慧电厂AI算法方案
智慧电厂AI算法方案通过深度学习和机器学习技术,实现设备故障预测、发电运行优化、安全监控和环保管理。方案涵盖平台层、展现层、应用层和基础层,具备精准诊断、智能优化、全方位监控等优势,助力电厂提升效率、降低成本、保障安全和环保合规。
326 2
智慧电厂AI算法方案
|
4月前
|
算法 数据可视化 BI
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
本程序基于免疫算法实现物流仓储点选址优化,并通过MATLAB 2022A仿真展示结果。核心代码包括收敛曲线绘制、最优派送路线规划及可视化。算法模拟生物免疫系统,通过多样性生成、亲和力评价、选择、克隆、变异和抑制机制,高效搜索最优解。解决了物流仓储点选址这一复杂多目标优化问题,显著提升物流效率与服务质量。附完整无水印运行结果图示。
137 20
基于免疫算法的最优物流仓储点选址方案MATLAB仿真
|
7月前
|
存储 算法 数据挖掘
重磅发布 | OpenSearch推出向量检索GPU图算法方案并支持GPU规格售卖
OpenSearch向量检索版推出了面向企业开发者的GPU图算法方案(CAGRA算法),支持客户直接购买GPU规格节点,是国内首家支持GPU规格的向量检索产品。
560 12
|
8月前
|
机器学习/深度学习 传感器 人工智能
智慧无人机AI算法方案
智慧无人机AI算法方案通过集成先进的AI技术和多传感器融合,实现了无人机的自主飞行、智能避障、高效数据处理及多机协同作业,显著提升了无人机在复杂环境下的作业能力和安全性。该方案广泛应用于航拍测绘、巡检监测、应急救援和物流配送等领域,能够有效降低人工成本,提高任务执行效率和数据处理速度。
407 2
智慧无人机AI算法方案
|
8月前
|
传感器 人工智能 监控
智慧化工厂AI算法方案
智慧化工厂AI算法方案针对化工行业生产过程中的安全风险、效率瓶颈、环保压力和数据管理不足等问题,通过深度学习、大数据分析等技术,实现生产过程的实时监控与优化、设备故障预测与维护、安全预警与应急响应、环保监测与治理优化,全面提升工厂的智能化水平和管理效能。
1151 0
智慧化工厂AI算法方案
|
8月前
|
存储 JSON 算法
TDengine 检测数据最佳压缩算法工具,助你一键找出最优压缩方案
在使用 TDengine 存储时序数据时,压缩数据以节省磁盘空间是至关重要的。TDengine 支持用户根据自身数据特性灵活指定压缩算法,从而实现更高效的存储。然而,如何选择最合适的压缩算法,才能最大限度地降低存储开销?为了解决这一问题,我们特别推出了一个实用工具,帮助用户快速判断并选择最适合其数据特征的压缩算法。
174 0