題目

https://leetcode.com/problems/shopping-offers/

題解

類似題目有：leetcode 474. Ones and Zeroes | 474. 一和零（雙約束背包問題）

本題實質上是一個多約束（n<6）的背包問題，求解目標是，在背包剛好裝滿的情況下，希望讓總的 price 最小。物品可以使用無限次。

參考左神體系班學習班第19節：剪貼紙問題（實際上沒參考它，只是想到有這么個題）

給定一個字符串str，給定一個字符串類型的數組arr，出現的字符都是小寫英文
arr每一個字符串，代表一張貼紙，你可以把單個字符剪開使用，目的是拼出str來
返回需要至少多少張貼紙可以完成這個任務。
例子：str= “babac”，arr = {“ba”,“c”,“abcd”}
ba + ba + c 3 abcd + abcd 2 abcd+ba 2
所以本題返回2

由于一些物品是以組合的形式給出的，所以我們先將 list 嵌套 list 轉化成數組，方便索引查找。
然后，因為物品可以單獨購買。為了統一方便，我們將可以單獨購買的物品也轉化成組合的形式，只不過讓它們的系數都為 1。

如下圖所示，前兩行分別是單獨購買 A 物品、單獨購買 B 的價格，后兩行是 AB 物品組合購買的價格。

然后就是經典的 暴力遞歸 -> 傻緩存了。本題應該是無法轉化成 dp 的，因為它的狀態太多了，詳見 dp map 中的 key，我的處理方式是將狀態壓縮成了字符串。后來看題解發現，hashmap 可以直接用 list 作為 key。

還有，我這個效率超級低，（應該是我為了避免回溯而copy的數組開銷比較大），刪掉 import 的頭文件的話，會超時（這又是 leetcode 的蜜汁特性，帶頭文件的話運行速度快一些），帶著頭文件可以 AC。

import java.util.HashMap; import java.util.List; import java.util.Map;class Solution {int M; // 套餐總數int N; // 物品總數public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {N = price.size();M = special.size() + price.size();// 數組化 套餐列表int[][] sp = new int[M][N + 1];for (int i = 0; i < special.size(); i++) {List<Integer> list = special.get(i);for (int j = 0; j < N + 1; j++) {sp[i][j] = list.get(j);}}for (int i = special.size(), j = 0; i < M; i++, j++) {sp[i][j] = 1;sp[i][N] = price.get(j);}// 數組化 購物清單int[] need = new int[N];for (int i = 0; i < N; i++) {need[i] = needs.get(i);}Map<String, Integer> dp = new HashMap<>();return process(sp, need, 0, dp);}// 多約束背包問題// 物品列表在special中。當前可選擇的物品在cur位置，還剩余needs要買的情況下，至少需要多少costpublic int process(int[][] special, int[] needs, int cur, Map<String, Integer> dp) {// 查緩存StringBuilder key = new StringBuilder();for (int n : needs) { // 狀態壓縮成字符串key.append(n).append(":");}key.append(cur);if (dp.containsKey(key.toString())) return dp.get(key.toString());if (allZero(needs)) {dp.put(key.toString(), 0);return 0;}int minCost = Integer.MAX_VALUE;for (int p = cur; p < M; p++) { // 當前購買special[p]套餐for (int count = 0; canBuy(special, needs, count, p); count++) { // 購買count件p套餐int[] newNeeds = buy(special, needs, count, p);int newCost = process(special, newNeeds, p + 1, dp);if (newCost != Integer.MAX_VALUE) {minCost = Math.min(minCost, count * special[p][N + 1 - 1] + newCost);}}}// 緩存dp.put(key.toString(), minCost);return minCost;}// 當前狀態下，如果繼續買count件p物品，是否買了不需要的public boolean canBuy(int[][] special, int[] needs, int count, int p) {for (int k = 0; k < N; k++) {if (needs[k] - count * special[p][k] < 0) return false;}return true;}public int[] buy(int[][] special, int[] needs, int count, int p) {int[] newNeeds = new int[N];for (int k = 0; k < N; k++) {newNeeds[k] = needs[k] - count * special[p][k];}return newNeeds;}public boolean allZero(int[] needs) {for (int n : needs) {if (n != 0) return false;}return true;}}

總結

以上是生活随笔為你收集整理的leetcode 638. Shopping Offers | 638. 大礼包（动态规划，多约束背包问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。