【力扣638】 大礼包问题 JAVA全过程详解，绝对易懂 |
您所在的位置：网站首页 › 大礼包pop字体 › 【力扣638】 大礼包问题 JAVA全过程详解，绝对易懂 |
【力扣638】 大礼包问题 JAVA全过程详解，绝对易懂
|
【前言】：本文讲解【力扣638 大礼包】的【动态规划】方法及其【记忆化搜索】的改进。 一、题目描述在 LeetCode 商店中，有 n 件在售的物品。每件物品 i 都有对应的价格，也有一些大礼包以优惠的价格捆绑销售一组物品。 1. 输入 一个整数数组 price 表示物品价格，其中 price [ i ] 是第 i 件物品的价格。 一个整数数组 needs 表示购物清单，其中 needs [ i ] 是需要购买第 i 件物品的数量。 一个数组 special 表示大礼包，special [ i ]的长度为 n + 1，其中 special [ i ][ j ] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special [ i ][ n ] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。 2. 输出 返回满足购物清单所需花费的最低价格。 你可以充分利用大礼包的优惠活动，但不能超出购物清单指定的数量，即使那样会降低整体价格。任意大礼包可无限次购买。 3. 要求 1 // 初始化全局变量 this.n = needs.size(); this.price = price; this.special = special; this.need = needs; return lowPrice(); } } 另外根据题干要求，只能按照需求量进行购买、而不能多买，所以需要完成一个辅助方法boolean canBuy ( List specialList )来判断在当前need下，传入的礼包specialList能否购买。 // 判断在当前need下，大礼包specialList能否购买 private boolean canBuy(List specialList) { for (int i = 0; i need.get(i)) return false; return true; }完成这两步铺垫就可以写计算函数int lowPrice()了。根据前面的分析讲解，首先要计算出直接购买这些商品所需的金额，然后再对每个大礼包进行判断，能购买则购买一次，并递归地计算出对应金额，算完所有的情况后，return所有可能的最小值就是该问题的解。这里要注意，每次购买礼包后、计算金额前，要将对应的需求量减去，而在计算完后再恢复原本的需求量，以免对后续计算造成影响。 // 计算直接购买和使用大礼包购买的所有情况的最小价格 private int lowPrice() { // 1. 首先计算不用大礼包，直接购买需要花的钱 int minPrice = 0; for (int i = 0; i private int n; private List price; private List special; private List need; public int shoppingOffers(List price, List special, List needs) { // 初始化全局变量 this.n = needs.size(); this.price = price; this.special = special; this.need = needs; return lowPrice(); } // 计算直接购买和使用大礼包购买的所有情况的最小价格 private int lowPrice() { // 1. 首先计算不用大礼包，直接购买需要花的钱 int minPrice = 0; for (int i = 0; i for (int i = 0; i need.get(i)) return false; return true; } } 三、改进版 - 记忆化搜索1. 缺陷分析 上述动态规划过程耗时较多的根本原因在于—— 各种情况的计算必然有个先后顺序，但事实上该问题的解与顺序无关！ 各种情况的计算必然有个先后顺序，但事实上该问题的解与顺序无关！ 各种情况的计算必然有个先后顺序，但事实上该问题的解与顺序无关！
在动态规划的思路分析中，购买礼包A后得到 f (5, 2, 2) + 16，计算 f (5, 2, 2) 时我们会发现还能购买一次礼包B，这样上述式子就变成了 f (2, 1, 0) + 30。于是我们算出 f (2, 1, 0) =7后知道，先购买一次礼包A、再购买一次礼包B、最后单独购买商品，一共花费¥37实现了6、4、5的购买任务。 而在购买礼包B得到 f (3, 3, 3) + 14后，计算 f (3, 3, 3) 时我们会继续购买一次礼包A得到 f (2, 1, 0) + 30，再根据 f (2, 1, 0) =7知道先购买一次礼包B、再购买一次礼包A、最后单独购买商品花费¥37完成任务。 也就是说，先购买A还是先购买B都一样，其实都是在计算 f (2, 1, 0) + 30。购买的路径（或者说顺序）对这个问题的解并没有影响，而先A后B和先B后A这2种等价的情况我们却做了多余的计算。 2. 优化解决 为了优化程序，我们引入【记忆化搜索】的思想。就像人拥有记忆一样，我们在先A后B的路径下已经算出了 f (2, 1, 0) =7， f (5, 2, 2) =21，那么在后续的路径中，一旦要用到 f (2, 1, 0) 和 f (5, 2, 2) 就能直接拿到结果而不用重复计算。 我们使用HashMap来记忆这些计算结果，HashMap可以存储 键key 到 值value 的映射关系，每算出一种需求量情形下的最优结果，我们就把该需求量及其结果存入HashMap以供下次使用。由于需求量被存放在数组 List need 中不能直接作为 键值key 使用，所以我们不妨把 need 转成 String 来描述，这样就确定了在类中引入一个全局变量map，存放String 到 Integer 的映射。 private HashMap map = new HashMap();有了映射关系，有了记忆的载体map，就要把记忆化体现在代码中。这里有个小技巧分享给大家，其实想引入记忆化并不需要对我们已经写好的动态规划函数 int lowPrice() 大兴土木，那样容易把自己绕晕出错，更好的解决办法是对 lowPrice() 再进行一次封装。 写一个新的函数 int memoLowPrice() ，在这个函数中，先去 map 里查询当前的 need 是否有已经求出的最优解，如果有就直接返回；如果没有再去调用 lowPrice() 计算最优解，并把当前 need 及其最优解的映射关系存入 map ，最后再返回最优解。这样的话，无记忆化的 int lowPrice() 和有记忆化的 int memoLowPrice() 在输入输出上是完全等价的，但却巧妙地插入了查询 map 和添加 map 的过程。 // 对lowPrice的封装，先查询map，如果已有结果直接返回，否则调用lowPrice计算后存入map再返回 private int memoLowPrice() { String keyStr = String.valueOf(need); if (map.containsKey(keyStr)) return map.get(keyStr); int temp = lowPrice(); map.put(keyStr, temp); return temp; }完成新函数 memoLowPrice() 后，把代码中凡是调用到 lowPrice() 的地方都替换成 memoLowPrice() 就大功告成。快把新代码交一发试试吧！记忆化后的完整代码如下，可直接通过该题。 |
【本文地址】