学习怎么做网站,怎样免费建立自己网站,开发网站建设的问卷调查,做脚本网站638. 大礼包
在 LeetCode 商店中#xff0c; 有 n 件在售的物品。每件物品都有对应的价格。然而#xff0c;也有一些大礼包#xff0c;每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格#xff0c;其中 price[i] 是第 i 件物品的价格。另有…638. 大礼包
在 LeetCode 商店中 有 n 件在售的物品。每件物品都有对应的价格。然而也有一些大礼包每个大礼包以优惠的价格捆绑销售一组物品。
给你一个整数数组 price 表示物品价格其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单其中 needs[i] 是需要购买第 i 件物品的数量。
还有一个数组 special 表示大礼包special[i] 的长度为 n 1 其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量且 special[i][n] 也就是数组中的最后一个整数为第 i 个大礼包的价格。
返回 确切 满足购物清单所需花费的最低价格你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品即使那样会降低整体价格。任意大礼包可无限次购买。
示例 1输入price [2,5], special [[3,0,5],[1,2,10]], needs [3,2]
输出14
解释有 A 和 B 两种物品价格分别为 ¥2 和 ¥5 。
大礼包 1 你可以以 ¥5 的价格购买 3A 和 0B 。
大礼包 2 你可以以 ¥10 的价格购买 1A 和 2B 。
需要购买 3 个 A 和 2 个 B 所以付 ¥10 购买 1A 和 2B大礼包 2以及 ¥4 购买 2A 。
示例 2输入price [2,3,4], special [[1,1,0,4],[2,2,1,9]], needs [1,2,1]
输出11
解释A B C 的价格分别为 ¥2 ¥3 ¥4 。
可以用 ¥4 购买 1A 和 1B 也可以用 ¥9 购买 2A 2B 和 1C 。
需要买 1A 2B 和 1C 所以付 ¥4 买 1A 和 1B大礼包 1以及 ¥3 购买 1B ¥4 购买 1C 。
不可以购买超出待购清单的物品尽管购买大礼包 2 更加便宜。提示
n price.lengthn needs.length1 n 60 price[i] 100 needs[i] 101 special.length 100special[i].length n 10 special[i][j] 50
解题思路
预处理special数组如果大礼包内所有的物品数量都为0或者大礼包的单价小于所有物品的总价则将其剔除出去。使用深度优先搜索每一次递归就是选择任意一份大礼包或者不购买大礼包全部按所需物品的单价购买计算购买该大礼包以后仍每种物品仍然需要的数量大小进行下一次递归如果超出购物清单指定数量的物品则不进行递归返回最小花费的组合方式。使用记忆化搜索使用map记录下所需物品清单和其花费最低价格的映射避免重复计算某种所需物品清单的最低价格。
代码
class Solution {MapListInteger, Integer map new HashMap();public int shoppingOffers(ListInteger price, ListListInteger special, ListInteger needs) {ListListInteger filter new ArrayList();for (ListInteger integerList : special) {int sum 0, c 0;for (int i 0; i integerList.size() - 1; i) {sum price.get(i) * integerList.get(i);c integerList.get(i);}if (integerList.get(integerList.size() - 1) sum c 0)filter.add(integerList);}return dfs(price, needs, filter);}public int dfs(ListInteger price, ListInteger needs, ListListInteger special) {if (map.containsKey(needs)) {return map.get(needs);}int p 0, n needs.size();for (int i 0; i needs.size(); i) {p needs.get(i) * price.get(i);}for (ListInteger spec : special) {ArrayListInteger next new ArrayList();for (int i 0; i n; i) {if (spec.get(i) needs.get(i)) {break;}next.add(needs.get(i) - spec.get(i));}if (next.size() n)p Math.min(p, spec.get(n) dfs(price, next, special));}map.put(needs, p);return p;}}
