Shopping Offers

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

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Thoughts

乍看上去和背包问题很像，挑offer和普通价格使得花钱最少。但没有一个物品列表却多了多种价格。

看了别人的答案，发现并没有少于指数级和没用DFS的答案。

DFS的思想比较直观，就是对每一个offer用一遍，如果用了后needs还有剩余，则继续用更新了的needs递归调用自己。由于价格不一定是用了offer的就一定便宜，而且还有可能有剩余的needs无法用offer，因此还要比较下不用offer时的价格。

Code

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int result = Integer.MAX_VALUE;
        // apply each offter to the needs, and recurse
        for(List<Integer> offer : special) {
            boolean valid = true;
            for (int j = 0; j < needs.size(); j++) {
                int remain = needs.get(j) - offer.get(j);
                needs.set(j, remain);
                if (valid && remain < 0) {
                    valid = false;
                }
            }

            if (valid) {
                result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(needs.size()));
            }
            for (int j = 0; j < needs.size(); j++) {
                int remain = needs.get(j) + offer.get(j);
                needs.set(j, remain);
            }
        }

        int nonOfferPrice = 0;
        for (int i = 0; i < needs.size(); i++) {
            nonOfferPrice += price.get(i) * needs.get(i);
        }

        return Math.min(result, nonOfferPrice);
    }
}

Analysis

时间复杂度是指数级。最差的情况是每个offer都是valid, 因此需要比较2^次n（选offer还是不选），n是special的长度。