本文主要是介绍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.
示例:
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.
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.
问题分析：
本题可以用dfs遍历每种可行的方案，得到花费最少的方案即是答案。
过程详见代码：
class Solution {
public:int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {int res = INT_MAX;dfs(price, special, needs, res, 0);return res;}void dfs(vector<int> price, vector<vector<int>> special, vector<int> needs,int& res,int sum) {vector<int> tneeds = needs;for (int i = 0; i < special.size(); i++){needs = tneeds;int j = 0;for (; j < needs.size(); j++){if (needs[j] < special[i][j]) break;}if (j < needs.size()) continue;for (j = 0; j < needs.size(); j++){needs[j] -= special[i][j];}dfs(price, special, needs, res, sum + special[i].back());}for (int j = 0; j < tneeds.size(); j++){sum += tneeds[j] * price[j];}if (sum < res) res = sum;}
};这篇关于Shopping Offers问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
