题目

类型：Bit Manipulation
image.png

解题思路

image.png

代码

  1. package bitManipulation;
  3. import java.util.*;
  5. public class ShoppingOffers {
  6.     Map<List<Integer>, Integer> memo = new HashMap<>();
  8.     public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
  9.         int n = price.size();
  11.         // 过滤不需要计算的大礼包，只保留需要计算的大礼包
  12.         List<List<Integer>> filterSpecial = new ArrayList<>();
  13.         for (List<Integer> sp : special) {
  14.             int totalCount = 0, totalPrice = 0;
  15.             for (int i = 0; i < n; ++i) {
  16.                 totalCount += sp.get(i);
  17.                 totalPrice += sp.get(i) * price.get(i);
  18.             }
  19.             if (totalCount > 0 && totalPrice > sp.get(n)) {
  20.                 filterSpecial.add(sp);
  21.             }
  22.         }
  24.         return dfs(price, special, needs, filterSpecial, n);
  25.     }
  27.     // 记忆化搜索计算满足购物清单所需花费的最低价格
  28.     public int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> curNeeds, List<List<Integer>> filterSpecial, int n) {
  29.         if (!memo.containsKey(curNeeds)) {
  30.             int minPrice = 0;
  31.             for (int i = 0; i < n; ++i) {
  32.                 minPrice += curNeeds.get(i) * price.get(i); // 不购买任何大礼包，原价购买购物清单中的所有物品
  33.             }
  34.             for (List<Integer> curSpecial : filterSpecial) {
  35.                 int specialPrice = curSpecial.get(n);
  36.                 List<Integer> nxtNeeds = new ArrayList<Integer>();
  37.                 for (int i = 0; i < n; ++i) {
  38.                     if (curSpecial.get(i) > curNeeds.get(i)) { // 不能购买超出购物清单指定数量的物品
  39.                         break;
  40.                     }
  41.                     nxtNeeds.add(curNeeds.get(i) - curSpecial.get(i));
  42.                 }
  43.                 if (nxtNeeds.size() == n) { // 大礼包可以购买
  44.                     minPrice = Math.min(minPrice, dfs(price, special, nxtNeeds, filterSpecial, n) + specialPrice);
  45.                 }
  46.             }
  47.             memo.put(curNeeds, minPrice);
  48.         }
  49.         return memo.get(curNeeds);
  50.     }
  52.     public static void main(String[] args) {
  53.         ShoppingOffers shoppingOffers = new ShoppingOffers();
  55.         List<Integer> price = Arrays.asList(2,5);
  56.         List<Integer> needs = Arrays.asList(3,2);
  57.         List<List<Integer>> special = Arrays.asList(Arrays.asList(3, 0, 5), Arrays.asList(1, 2, 10));
  58.         System.out.println(shoppingOffers.shoppingOffers(price, special, needs));
  59.     }
  60. }