动态规划-638-Shopping Offers

96 阅读 0 评论 64 点赞

我是靠谱客的博主不安猫咪，最近开发中收集的这篇文章主要介绍动态规划-638-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.

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.

问题描述:
在leetcode商店中，有各种各样的物品出售，每个物品都有对应的价格。
现在有促销套餐，每个套餐对应若干个一种或多种物品，伴随对应的价格。
现在，给定每个物品的价格，每种套餐以及你所需要购买的每个物品的数量，返回你需要花费的最少的钱
注意，可以使用任意多的套餐

例子:
给定输入:
[2,5],代表两种物品A和B，A要2元，B要5元
[[3,0,5],[1,2,10]]，对应两个套餐，1套餐花5元买3个A和0个B，2套餐花10元买1个A和2个B
[3, 2]，代表你需要购买的A,B的数目分别为3,2
输出:14元
解释:
你可以选择2套餐一份，然后单独买两个两个A

问题分析:
使用回溯法。注意问题描述里面的一句话:
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.
需要买恰好规定数量的物品，不能少也不能多

解法:

class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return helper(price, special, needs, 0);
    }

    private int helper(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int start) {
        int min = buyDirectly(price, needs);
        for(int i = start; i < special.size(); i++) {
            if(isValid(special.get(i), needs)) {
                List<Integer> newNeeds = new ArrayList<>();
                for(int j = 0; j < needs.size(); j++) {
                    newNeeds.add(needs.get(j) - special.get(i).get(j));
                }
                //next start will still be i
                min = Math.min(min, helper(price, special, newNeeds, i) + special.get(i).get(needs.size()));
            }
        }
        return min;
    }

    private boolean isValid(List<Integer> offer, List<Integer> needs) {
        for(int i = 0; i < offer.size() - 1; i++) {
            if(offer.get(i) > needs.get(i)) {
                return false;
            }
        }
        return true;
    }

    private int buyDirectly(List<Integer> price, List<Integer> needs) {
        int sum = 0;
        for(int i = 0; i < price.size(); i++) {
            sum += price.get(i) * needs.get(i);
        }
        return sum;
    }
}