LeetCode Shopping Offers 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. Example 1:
Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14 Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively. In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay $10 for 1A and 2B. You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.Example 2:
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1] Output: 11 Explanation: The price of A is $2, and $3 for B, $4 for C. You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. You cannot add more items, though only $9 for 2A ,2B and 1C.Note:
- There are at most 6 kinds of items, 100 special offers.
- For each item, you need to buy at most 6 of them.
- You are not allowed to buy more items than you want, even if that would lower the overall price.
给定每个商品的单价和需要购买的数量，并且有一些special offer，相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品，所花的最低费用是多少。 注意给定的限制条件中商品最多只有6种，且每件最多只购买6件，所以可以考虑用暴力方法。 把special offer看成一个背包问题里的“商品”，对于每个special offer，我们有两种选择，可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项，即可以用该special offer，我们比较用和不用该special offer的最终花费，取花费低的。如果用该special offer，则needs数组需要减掉sp捆绑的每件商品的件数，然后继续递归该sp是否可用，相当于完全背包，不计件数的。如果该sp不能用，则递归考虑下一个sp。最后如果递归考虑完所有sp了，则剩余的商品只能按原价购买，算出按原价购买的费用即可。 完整代码如下： [cpp] class Solution { private: int dot(vector<int>& price, vector<int>& needs) { int ans = 0; for (int i = 0; i < needs.size(); ++i) { ans += price[i] * needs[i]; } return ans; } int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) { if (idx == special.size())return dot(price, needs); // 原价购买 int i = 0, n = special[idx].size(); vector<int> small_needs = needs; for (i = 0; i < n – 1; ++i) { if (special[idx][i] > needs[i])break; small_needs[i] -= special[idx][i]; } if (i == n – 1)return min(shopping(price, special, small_needs, idx) + special[idx][n – 1], shopping(price, special, needs, idx + 1)); else return shopping(price, special, needs, idx + 1); } public: int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { return shopping(price, special, needs, 0); } }; [/cpp] 本代码提交AC，用时6MS。 参考：https://leetcode.com/articles/shopping-offers/，下次记得看到这种数据量非常小的题，首先尝试暴力方法！]]>