使用「换元一维优化」方式求解完全背包|Java 刷题打卡

简介: 使用「换元一维优化」方式求解完全背包|Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的518. 零钱兑换 II,难度为 Medium


给定不同面额的硬币和一个总金额。


写出函数来计算可以凑成总金额的硬币组合数。


假设每一种面额的硬币有无限个。


示例 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
解释: 只用面额2的硬币不能凑成总金额3。
复制代码


示例 3:


输入: amount = 10, coins = [10] 
输出: 1
复制代码


注意:


你可以假设:


  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数


完全背包(朴素解法)



在上一题 [322. 零钱兑换] 中,我们求的是「取得特定价值所需要的最小物品个数」。


对于本题,我们求的是「取得特定价值的方案数量」。


求的东西不一样,但问题的本质没有发生改变,同样属于「组合优化」问题。


你可以这样来理解什么是「组合问题」:


被选物品之间不需要满足特定关系,只需要选择物品,以达到「全局最优」或者「特定状态」即可。


同时硬币相当于我们的物品,每种硬币可以选择「无限次」,很自然的想到「完全背包」。


这时候可以将「完全背包」的状态定义搬过来进行“微调”:


定义 f[i][j]f[i][j] 为考虑前 ii 件物品,凑成总和为 jj 的方案数量。


为了方便初始化,我们一般让 f[0][x]f[0][x] 代表不考虑任何物品的情况。


因此我们有显而易见的初始化条件:f[0][0] = 1f[0][0]=1,其余 f[0][x] = 0f[0][x]=0


代表当没有任何硬币的时候,存在凑成总和为 0 的方案数量为 1;凑成其他总和的方案不存在。


当「状态定义」与「基本初始化」有了之后,我们不失一般性的考虑 f[i][j]f[i][j] 该如何转移。


对于第 ii 个硬币我们有两种决策方案:


  • 不使用该硬币:

f[i][j] = f[i - 1][j]f[i][j]=f[i1][j]

  • 使用该硬币:由于每个硬币可以被选择多次(容量允许的情况下),因此方案数量应当是选择「任意个」该硬币的方案总和:


f[i][j] = \sum_{k = 1}^{\left \lfloor {j / val} \right \rfloor}f[i - 1][j - k * val], val = nums[i - 1]f[i][j]=k=1j/valf[i1][jkval],val=nums[i1]


代码:


class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[][] f = new int[n + 1][cnt + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = 0; j <= cnt; j++) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * val <= j; k++) {
                    f[i][j] += f[i - 1][j - k * val];  
                }
            }
        }
        return f[n][cnt];
    }
}
复制代码


  • 时间复杂度:共有 n * cntncnt 个状态需要转移,每个状态转移最多遍历 cntcnt 次。整体复杂度为 O(n * cnt^2)O(ncnt2)
  • 空间复杂度:O(n * cnt)O(ncnt)


完全背包(一维优化)



显然二维完全背包求解方案复杂度有点高。


nn 的数据范围为 10^2102cntcnt 的数据范围为 10^3103,总的计算量为 10^8108 以上,处于超时边缘(实际测试可通过)。


我们需要对其进行「降维优化」,可以使用最开始讲的 数学分析方式,或者上一讲讲的 换元优化方式 进行降维优化。


由于 数学分析方式 十分耗时,我们用得更多的 换元优化方式。两者同样具有「可推广」特性。


因为后者更为常用,所以我们再来回顾一下如何进行 换元一维优化


  1. 在二维解法的基础上,直接取消「物品维度」
  2. 确保「容量维度」的遍历顺序为「从小到大」(适用于「完全背包」)
  3. 将形如 f[i - 1][j - k * val]f[i1][jkval] 的式子更替为 f[j - val]f[jval],同时解决「数组越界」问题(将物品维度的遍历修改为从 valval 开始)


代码:


class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[] f = new int[cnt + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = val; j <= cnt; j++) {
                f[j] += f[j - val];
            }
        }
        return f[cnt];
    }
}
复制代码


  • 时间复杂度:共有 n * cntncnt 个状态需要转移,整体复杂度为 O(n * cnt)O(ncnt)
  • 空间复杂度:O(cnt)O(cnt)


总结



[322. 零钱兑换] 和 本篇的「518. 零钱兑换 II」本质是一样的。


之所将两题分开成两篇【练习】,主要是为了加强大家对于「一维优化」的熟练度。


上来先写一个「二维朴素版」然后再进行「数学分析」推导这样的做法太慢了,不适合于比赛或者笔试情景。


我们应当做到:上手就能写出「一维优化」版本,但同时在脑中思考的是二维的递推逻辑 ~


最后



这是我们「刷穿 LeetCode」系列文章的第 No.518 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
15天前
|
Java Spring
如何优化Java异步任务的性能?
本文介绍了Java中四种异步任务实现方式:基础Thread、线程池、CompletableFuture及虚拟线程。涵盖多场景代码示例,展示从简单异步到复杂流程编排的演进,适用于不同版本与业务需求,助你掌握高效并发编程实践。(239字)
125 6
|
21天前
|
数据采集 存储 弹性计算
高并发Java爬虫的瓶颈分析与动态线程优化方案
高并发Java爬虫的瓶颈分析与动态线程优化方案
|
2月前
|
安全 Java 编译器
new出来的对象,不一定在堆上?聊聊Java虚拟机的优化技术:逃逸分析
逃逸分析是一种静态程序分析技术,用于判断对象的可见性与生命周期。它帮助即时编译器优化内存使用、降低同步开销。根据对象是否逃逸出方法或线程,分析结果分为未逃逸、方法逃逸和线程逃逸三种。基于分析结果,编译器可进行同步锁消除、标量替换和栈上分配等优化,从而提升程序性能。尽管逃逸分析计算复杂度较高,但其在热点代码中的应用为Java虚拟机带来了显著的优化效果。
63 4
|
2月前
|
存储 人工智能 算法
Java 大视界 -- Java 大数据在智能医疗影像数据压缩与传输优化中的技术应用(227)
本文探讨 Java 大数据在智能医疗影像压缩与传输中的关键技术应用,分析其如何解决医疗影像数据存储、传输与压缩三大难题,并结合实际案例展示技术落地效果。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据机器学习模型在生物信息学基因功能预测中的优化与应用(223)
本文探讨了Java大数据与机器学习模型在生物信息学中基因功能预测的优化与应用。通过高效的数据处理能力和智能算法,提升基因功能预测的准确性与效率,助力医学与农业发展。
|
2月前
|
数据采集 搜索推荐 Java
Java 大视界 -- Java 大数据在智能教育虚拟学习环境构建与用户体验优化中的应用(221)
本文探讨 Java 大数据在智能教育虚拟学习环境中的应用,涵盖多源数据采集、个性化推荐、实时互动优化等核心技术,结合实际案例分析其在提升学习体验与教学质量中的成效,并展望未来发展方向与技术挑战。
|
2月前
|
机器学习/深度学习 算法 Java
Java 大视界 -- Java 大数据在智能物流运输车辆智能调度与路径优化中的技术实现(218)
本文深入探讨了Java大数据技术在智能物流运输中车辆调度与路径优化的应用。通过遗传算法实现车辆资源的智能调度,结合实时路况数据和强化学习算法进行动态路径优化,有效提升了物流效率与客户满意度。以京东物流和顺丰速运的实际案例为支撑,展示了Java大数据在解决行业痛点问题中的强大能力,为物流行业的智能化转型提供了切实可行的技术方案。
Java 数据库 Spring
59 0
|
1月前
|
算法 Java
Java多线程编程:实现线程间数据共享机制
以上就是Java中几种主要处理多线程序列化资源以及协调各自独立运行但需相互配合以完成任务threads 的技术手段与策略。正确应用上述技术将大大增强你程序稳定性与效率同时也降低bug出现率因此深刻理解每项技术背后理论至关重要.
92 16
|
2月前
|
缓存 并行计算 安全
关于Java多线程详解
本文深入讲解Java多线程编程,涵盖基础概念、线程创建与管理、同步机制、并发工具类、线程池、线程安全集合、实战案例及常见问题解决方案,助你掌握高性能并发编程技巧,应对多线程开发中的挑战。

热门文章

最新文章