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.

思路分析：

题目要求解的是在可重复使用优惠券的情况下，恰好购买指定数量的商品的最低价格。考虑到优惠券可以多次使用，而且购买商品的数量是一定的，因此我们可以选择递归的思想解决问题：先计算出不使用优惠券下，购买商品的总价格total；假设每张优惠券可用canUse=true，遍历每张优惠券，如果优惠券中某商品的数量大于needs中该商品的数量，则canUse=false，否则就计算出使用该优惠券后的总价格temprice（修改needs并调用shoppingOffers函数，再加上优惠券的价格）和之前的价格total，取最小值。

代码实现：

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int total = 0;
        int temprice = 0;
        for (int i = 0; i < needs.size(); i++) {
            total += price[i] * needs[i];
        }
        for (auto coupon : special) {
            bool canUse = true;     //初始化每张优惠券可以使用
            for (int j = 0; j < needs.size(); j++) {
                //需要的item小于提供的item，优惠券不可用
                if (coupon[j] > needs[j]) {
                    canUse = false;
                } 
                needs[j] = needs[j] - coupon[j];
            }
            if (canUse) {
                //使用优惠券的总价格=剩余items的价格+优惠券的价格
                temprice = shoppingOffers(price, special, needs) + coupon.back();
                //使用优惠券和不使用优惠券，价格取最小值
                total = min(total, temprice);
            }
            //恢复needs，遍历其余优惠券，找到价格的最小值
            for (int k = 0; k < needs.size(); k++) {
                needs[k] = needs[k] + coupon[k];
            }
        }
        return total;
    }
};