• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
• This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode – 638 – package

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

In the LeetCode store, there are n items for sale. There is a price for each item. However, there are also gift packages, each bundled with a group of items at a favorable price.

You are given an integer array price representing the price of the item, where price[I] is the price of the ith item. Another integer array needs represents the shopping list, where needs[I] is the quantity of the ith item that needs to be purchased.

The length of special[I] is n + 1, where special[I][j] represents the number of JTH items in the ith gift package. And special[I][n] (the last integer in the array) is the price of the i-th package.

Return the exact lowest price you need to spend to meet your shopping list, and you can take advantage of the great deals on gift packages. You can’t buy more than the specified amount on your shopping list, even if that lowers the overall price. Unlimited purchase of any gift package.

Example 1:

Price = [2,5], special = [3,0,5],[1,2,10], needs = [3,2] Gift pack 1, you can buy 3A and 0B for ¥5. Gift pack 2, you can buy 1A and 2B for ¥10. You need to buy 3 A's and 2B's, so pay ¥10 for 1A and 2B (gift pack 2), and ¥4 for 2A.Copy the code

Example 2:

Price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1] You can buy 1A and 1B with ¥4, as well as 2A, 2B and 1C with ¥9. Need to buy 1A, 2B and 1C, so pay ¥4 for 1A and 1B (gift pack 1), and ¥3 for 1B, ¥4 for 1C. You can't buy more than what's on your to-do list, although it's cheaper to buy gift pack 2.Copy the code

Tip:

• n == price.length
• n == needs.length
• 1 <= n <= 6
• 0 <= price[i] <= 10
• 0 <= needs[i] <= 10
• 1 <= special.length <= 100
• special[i].length == n + 1
• 0 <= special[i][j] <= 50

Idea 1: DFS

• There are two forms of purchase for each item
• One is a single purchase, the other is a gift package purchase
• The single purchase is preprocessed and then converted to another package
• How many DFS can be preprocessed into the package
• This uses mitsuha’s code

class Solution {
    int ans = 0x3f3f3f3f;
    List<Integer> price, needs;
    List<List<Integer>> special;
    Map<Integer, Integer> map = new HashMap<>();
    int n, m;

    public int shoppingOffers(List<Integer> _price, List<List<Integer>> _special, List<Integer> _needs) {
        price = _price;
        special = _special;
        needs = _needs;
        n = price.size();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) temp.add(0);
        for (int i = 0; i < n; i++) {
            List<Integer> clone = new ArrayList<>(temp);
            clone.set(i, 1);
            clone.add(price.get(i));
            special.add(clone);
        }
        m = special.size();
        for (int i = 0; i < m; i++) {
            List<Integer> x = special.get(i);
            int min = -1;
            for (int j = 0; j < n; j++) {
                int a = x.get(j), b = needs.get(j);
                if (a == 0 || b == 0) continue;
                if (min == -1) min = b / a;
                else min = Math.min(min, b / a);
            }
            map.put(i, Math.max(min, 0));
        }
        dfs(0, needs, 0);
        return ans;
    }

    void dfs(int u, List<Integer> list, int cur) {
        if (cur >= ans) return;
        if (u == m) {
            for (int i = 0; i < n; i++) {
                if(list.get(i) ! =0) return;
            }
            ans = Math.min(ans, cur);
            return;
        }
        List<Integer> x = special.get(u);
        out:
        for (int k = 0; k <= map.get(u); k++) {
            List<Integer> clist = new ArrayList<>(list);
            for (int i = 0; i < n; i++) {
                int a = x.get(i), b = clist.get(i);
                if (a * k > b) break out;
                clist.set(i, b - a * k);
            }
            dfs(u + 1, clist, cur + k * x.get(n)); }}}Copy the code

• This time complexity is amazing to me, because I can’t figure it out
• Space complexity O(km+nk^{m+n}km+n)