ShoppingOffers [source code]
public class ShoppingOffers {
static
/******************************************************************************/
class Solution {
int minTotal;
int curTotal;
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> _needs) {
minTotal = Integer.MAX_VALUE;
curTotal = 0;
assert price.size () == _needs.size ();
int N = price.size ();
int[] prices = new int[N], needs = new int[N];
for (int i = 0; i < N; i++) {
prices[i] = price.get (i);
needs[i]= _needs.get (i);
}
int M = special.size ();
int[][] specials = new int[M][N + 1];
for (int i = 0; i < M; i++) {
List<Integer> offer = special.get (i);
assert offer.size () == N + 1;
for (int j = 0; j < N + 1; j++) {
specials[i][j] = offer.get (j);
}
}
int[] specialTakes = new int[M], specialCounts = new int[N];
for (int i = 0; i < N; i++)
curTotal += prices[i] * needs[i];
dfs (prices, needs, specials, specialTakes, specialCounts);
return minTotal;
}
void dfs (int[] prices, int[] needs, int[][] specials, int[] specialTakes, int[] specialCounts) {
if (curTotal < minTotal)
minTotal = curTotal;
int N = prices.length, M = specials.length;
for (int i = 0; i < M; i++) {
boolean canInc = true;
for (int j = 0; j < N; j++) {
if (specialCounts[j] + specials[i][j] > needs[j]) {
canInc = false;
break;
}
}
if (canInc) {
updateOffer (true, i, prices, needs, specials, specialTakes, specialCounts);
dfs (prices, needs, specials, specialTakes, specialCounts);
updateOffer (false, i, prices, needs, specials, specialTakes, specialCounts);
}
}
}
void updateOffer (boolean increasing, int offerIndex, int[] prices, int[] needs, int[][] specials, int[] specialTakes, int[] specialCounts) {
int increment = increasing ? 1 : -1;
specialTakes[offerIndex] += increment;
curTotal += increment * specials[offerIndex][specialCounts.length];
for (int i = 0; i < specialCounts.length; i++) {
specialCounts[i] += increment * specials[offerIndex][i];
curTotal -= increment * (specials[offerIndex][i] * prices[i]);
}
}
}
/******************************************************************************/
public static void main(String[] args) {
ShoppingOffers.Solution tester = new ShoppingOffers.Solution();
Integer[][] priceInputs = {
{2,5},
{2,3,4},
};
Integer[][][] specialInputs = {
{{3,0,5}, {1,2,10}},
{{1,1,0,4},{2,2,1,9}},
};
Integer[][] needInputs = {
{3,2},
{1,2,1},
};
Integer[] answers = {
14,
11,
};
for (int i = 0; i < specialInputs.length; i++) {
List<Integer> prices = Arrays.asList (priceInputs[i]), needs = Arrays.asList (needInputs[i]);
List<List<Integer>> special = new ArrayList<> ();
for (Integer[] offer : specialInputs[i])
special.add (Arrays.asList (offer));
int ans = answers[i];
System.out.println (Printer.separator ());
int output = tester.shoppingOffers (prices, special, needs);
System.out.printf ("%s and %s and %s -> %s, expected: %d\n",
Printer.array (priceInputs[i]), '\n' + Matrix.printMatrix (specialInputs[i]), Printer.array (needInputs[i]),
Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
);
}
}
}
题目意思本身并不难, 但是思路暂时还没有;
另外可以看到, 如果你给每一个special offer被采纳的次数一个变量, 这个问题最后其实就是一个linear programming的问题; 不过有没有现成的算法可以解这个呢?
不过真的要写, 看到这里之后, 一个DFS或者类似backtracking的算法其实是不难的, 但是这题的DP算法是什么思路?
如果是一个DP的算法, 一般要能找到一个subproblem结构, 也就是找到一个类似N的变量, 可以减小的变量, 这样才有一个assemble的过程; 但是这题感觉这个变量很难找到;
还是先用DFS尝试写一下;
这题如果用DFS来做, 感觉就是考察你对各种matrix运算的熟练度; 本来我已经写的头皮稀昏, 不过没想到居然一发直接AC, 虽然时间还是超了. 速度很好, 是11ms (95%).
另外, 吸取之前刚做完的一题DFS的教训, 这次我的do/undo操作直接都放在了pre-node的位置, 而不是node自己的iteration的body里面;
editorial
Approach #1 Using Recursion [Accepted]
public class Solution {
public int shoppingOffers(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
return shopping(price, special, needs);
}
public int shopping(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
int j = 0, res = dot(needs, price);
for (List < Integer > s: special) {
ArrayList < Integer > clone = new ArrayList < > (needs);
for (j = 0; j < needs.size(); j++) {
int diff = clone.get(j) - s.get(j);
if (diff < 0)
break;
clone.set(j, diff);
}
if (j == needs.size())
res = Math.min(res, s.get(j) + shopping(price, special, clone));
}
return res;
}
public int dot(List < Integer > a, List < Integer > b) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i) * b.get(i);
}
return sum;
}
}
这个跟我的思路其实是差不多的; 只不过他对于返回值的设计更加合理, 所以不需要借助于global变量来完成一个找最值的过程; 严格来说这题确实是一个这样的普通的recursion就能完成, 而不需要专门去做一个backtracking的算法;
### Approach #2 Using Recursion with memoization [Accepted]
```java
public class Solution {
public int shoppingOffers(List < Integer > price, List < List < Integer >> special, List < Integer > needs) {
Map < List < Integer > , Integer > map = new HashMap();
return shopping(price, special, needs, map);
}
public int shopping(List < Integer > price, List < List < Integer >> special, List < Integer > needs, Map < List < Integer > , Integer > map) {
if (map.containsKey(needs))
return map.get(needs);
int j = 0, res = dot(needs, price);
for (List < Integer > s: special) {
ArrayList < Integer > clone = new ArrayList < > (needs);
for (j = 0; j < needs.size(); j++) {
int diff = clone.get(j) - s.get(j);
if (diff < 0)
break;
clone.set(j, diff);
}
if (j == needs.size())
res = Math.min(res, s.get(j) + shopping(price, special, clone, map));
}
map.put(needs, res);
return res;
}
public int dot(List < Integer > a, List < Integer > b) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
sum += a.get(i) * b.get(i);
}
return sum;
}
}
这里他的做法相对于我的思路的优势就体现出来了, 因为他这里这个算法是一个普通的recursion而不是一个backtracking, 所以加memo就非常的简单; 这个也是以前总结过的, 如果想要让加memo变得简单, 一般要求你的recursion:
- input可以hash;
- 有明确的返回值;
要满足这两点, 一个必要条件就是有明确的subproblem结构;
这里他主要观察到的一个intuition就是order does not matter. 我回头想了一下, 我自己上面的算法实际上是没有利用到这个性质的;
为什么我当时没有想到这个recursion的版本? 一个原因就是我没有去思考这个subproblem结构; 他注意到了这里设计subproblem结构的关键是让needs不断的缩小, 这个也是任何DP问题的关键;
discussion最优解:
@jaqenhgar said in Simple Java recursive solution:
The basic idea is to pick each offer, and subtract the needs. And then compute the price without the offer.
Pick whichever is minimum.Edit : ) much appreciated if someone can shorten the code with Java8 :)
```java
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int result = Integer.MAX_VALUE;
//apply each offer to the needs, and recurse
for(int i = 0; i < special.size(); i++) {
List<Integer> offer = special.get(i);
boolean invalidOffer = false;
for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
int remain = needs.get(j) - offer.get(j);
needs.set(j, remain);
if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
}
if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(needs.size()));
}
for(int j = 0; j < needs.size(); j++) { // reset the needs
int remain = needs.get(j) + offer.get(j);
needs.set(j, remain);
}
}
// choose b/w offer and non offer
int nonOfferPrice = 0;
for(int i = 0; i < needs.size(); i++) {
nonOfferPrice += price.get(i) * needs.get(i);
}
return Math.min(result, nonOfferPrice);
}
这个就是很普通的backtracking; 不过因为他设计了有效的返回值, 所以这个算法其实是可以加memo的;
>
> **`UPDATE 1` :** For the below test case, we get time limit exceeded since it's exponential. TLE due to needs=30+.
> I've requested admins to add this testcase.
>
[2,5]
[[1,0,5],[1,2,10]]
[39,39]```
So I made some optimization to reduce the recursive calls, by precomputing the number of times offer can be applied.See UPDATE 3, there's an example that breaks this greedy optimization.```java
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
int result = Integer.MAX_VALUE;
//apply each offer to the needs, and recurse
for(int i = 0; i < special.size(); i++) {
List<Integer> offer = special.get(i);
boolean invalidOffer = false;
int offerCount = Integer.MAX_VALUE; // number of times offer can be applied
for(int j = 0; j < needs.size(); j++) { // pre-compute number of times offer can be called
int remain = needs.get(j) - offer.get(j);
if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
if(offer.get(j) > 0)
offerCount = Math.min(offerCount, needs.get(j)/offer.get(j));
}
for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
int remain = needs.get(j) - offer.get(j) * offerCount;
needs.set(j, remain);
}
if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
result = Math.min(result, shoppingOffers(price, special, needs) + (offerCount * offer.get(needs.size())));
}
for(int j = 0; j < needs.size(); j++) { // reset the needs
int remain = needs.get(j) + offer.get(j) * offerCount;
needs.set(j, remain);
}
}
// choose b/w offer and non offer
int nonOfferPrice = 0;
for(int i = 0; i < needs.size(); i++) {
nonOfferPrice += price.get(i) * needs.get(i);
}
return Math.min(result, nonOfferPrice);
}
这个算法改进的目的很简单, 就是希望减少recursion的level的数量; 他的做法就是在每一个level, 尽可能greedy, 也就是能拿多少这个offer就拿多少; 但是这个greedy的做法是很难被justify的;
>
> **`UPDATE 2:`** I think OJ is breaking with the below test case. My code handles it though. Expected output is 8000, since it has two items of 1$ each. I've requested to add the test case. Also, another assumption is that result doesn't exceed Integer.MAX_VALUE. @administrators
>
[1,1]
[[1,1,2],[1,1,3]]
[4000,4000]**`UPDATE 3:`** From @Red_Eden 's thought, I found a test case that breaks my optimization. OJ is missing this test as well. My solution gives answer = 6, but actual is pick one offer just once = 4.[500]
[[2,1],[3,2],[4,1]]
[9]```
另外一个类似的版本:
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
Map<List<Integer>, Integer> dp = new HashMap<>();
List<Integer> allZero = new ArrayList<>();
for(int i=0;i<needs.size();i++) {
allZero.add(0);
}
dp.put(allZero, 0);
return dfs(needs, price, special, dp);
}
private int dfs(List<Integer> needs, List<Integer> price, List<List<Integer>> special, Map<List<Integer>, Integer> dp) {
if(dp.containsKey(needs)) return dp.get(needs);
int res = Integer.MAX_VALUE;
for(List<Integer> s : special) {
List<Integer> needsCopy = new ArrayList<>(needs);
boolean valid = true;
for(int i=0;i<needs.size();i++) {
needsCopy.set(i, needsCopy.get(i) - s.get(i));
if(needsCopy.get(i) < 0) {
valid = false;
break;
}
}
if(valid) {
res = Math.min(res, s.get(needs.size()) + dfs(needsCopy, price, special, dp));
}
}
//What if we do not use specials? specials can be deceiving,
//perhaps buying using regular prices is cheaper.
int noSpecial = 0;
for(int i=0;i<needs.size();i++) {
noSpecial += needs.get(i) * price.get(i);
}
res = Math.min(res, noSpecial);
dp.put(needs, res);
return res;
}
comment给的比较详细;
另外, 大部分这里的有memo的解法, 都利用了之前讨论过的hash of collection的技巧, 这里是一个人的讨论:
@chao59 said in Java DFS + DP:
@Nakanu
List's hashCode method is defined here.As the stackoverflow discussion points out, it generally is a bad idea to use Lists as map keys, since the hashCode will change once you mutate the List. But in this solution, Lists will have the same contents when Map::get and Map::put are called.
The solution actually relies on the fact that two Lists with same contents generate the same hashCode. It is very easy to test it. Try setting your "needs" list as all zeros, and you know "allZero" and "needs" are different Objects, but the first call of dp.containsKey(needs) still returns true because "allZero" and "needs" have the same contents.
所以这个东西用起来还是稍微要小心一点的, 尤其是注意最好不要有mutation.
对应的, 有人认为这题其实也可以自己写一个专门的hash:
@tiandiao123 said in Java DFS + DP:
You can create your own hashcode function in this case since there are no more than 6 of each item in this question, so slightly modify your method:
```java
public class Solution {
public int shoppingOffers(List
Map
map.put(0,0);
return searchMinPay(price,special,needs,map);
}
public int searchMinPay(List<Integer> price,List<List<Integer>> special,List<Integer> needs,Map<Integer,Integer> map){
int hashkey=hash(needs);
if(map.containsKey(hashkey)){
return map.get(hashkey);
}
int res=0;
for(int i=0;i<needs.size();i++){
int count=needs.get(i);
res+=count*price.get(i);
}
for(List<Integer> ele:special){
boolean valid=true;
List<Integer> copyneeds=new ArrayList<>(needs);
for(int i=0;i<copyneeds.size();i++){
if(copyneeds.get(i)>=ele.get(i)){
copyneeds.set(i,copyneeds.get(i)-ele.get(i));
}else{
valid=false;
break;
}
}
if(valid){
res=Math.min(res,searchMinPay(price,special,copyneeds,map)+ele.get(needs.size()));
}
}
map.put(hashkey,res);
return res;
}
public int hash(List<Integer> list){
int num=0;
for(int i=0;i<list.size();i++){
num=num*7+list.get(i);
}
return num;
}
}
倒不是说这个是严格必须的, 只不过告诉你, 这个办法可行; 虽然加了一点overhead(每次查表之前都要自己专门算一次hash), 但是在搜索空间比较大的时候, 这个东西还是利大于弊的;
---
另外一个类似的解法, 没有转array也没有加memo, 但是速度居然给我的解法是一样的:
@quincyhehe said in [Very Easy to understand JAVA Solution beats 95% with explanation](https://discuss.leetcode.com/post/201093):
> The idea is very similar to combination sum. In combination sum where each element can be repeated, check each element to see if it can be used (in this case, if the sum doesn't exceed the target). If so, use it. Repeat this until we get the result.
>
> For this question, we check each promotion offers, if the offer can be used, use it. Repeat the process and find the minimum result. In this question, the condition whether one offer can be used is the number of items in the offer doesn't exceed the needed number. Find the minimum among all combinations.
>
> The thing to remember, which also happens in real life is that some special offers are actually more expensive than buying each individual item in the offers!!! Thus be smart and compare if buying directly is cheaper.
>
> here is my code:
>
```java
public 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 pos) {
int local_min = directPurchase(price, needs);
for (int i = pos; i < special.size(); i++) {
List<Integer> offer = special.get(i);
List<Integer> temp = new ArrayList<Integer>();
for (int j= 0; j < needs.size(); j++) {
if (needs.get(j) < offer.get(j)) { // check if the current offer is valid
temp = null;
break;
}
temp.add(needs.get(j) - offer.get(j));
}
if (temp != null) { // use the current offer and try next
local_min = Math.min(local_min, offer.get(offer.size() - 1) + helper(price, special, temp, i));
}
}
return local_min;
}
private int directPurchase(List<Integer> price, List<Integer> needs) {
int total = 0;
for (int i = 0; i < needs.size(); i++) {
total += price.get(i) * needs.get(i);
}
return total;
}
}
看起来反正是跟之前的解法没有太大的区别的;
这题我的一个失误是没有看出来对needs不断进行缩小来得到一个subproblem结构, 看了一下discussion的解法, 基本都看到了这个关键结构;
submission最优解: 10(98):
class Solution {
List<Integer> price;
List<List<Integer>> special;
boolean allzero(int[] needs) {
for (int i: needs) {
if (i != 0) return false;
}
return true;
}
boolean lessThan(List<Integer> l1, int a, int[] l2) {
for (int i = 0; i < l2.length; i++) {
if (l1.get(i) * a > l2[i]) return false;
}
return true;
}
void minus(List<Integer> l1, int a, int[] l2) {
for (int i = 0; i < l2.length; i++) {
l2[i] -= a * l1.get(i);
}
}
void add(List<Integer> l1, int a, int[] l2) {
for (int i = 0; i < l2.length; i++) {
l2[i] += a * l1.get(i);
}
}
int buy(int idx, int[] needs) {
if (allzero(needs)) return 0;
if (idx >= special.size()) {
int sum = 0;
for (int i = 0; i < needs.length; i++) {
sum += price.get(i) * needs[i];
}
return sum;
}
int min = buy(idx + 1, needs);
for (int i = 1; lessThan(special.get(idx), i, needs); i++) {
minus(special.get(idx), i, needs);
int tmp = buy(idx + 1, needs) + i * special.get(idx).get(needs.length);
if (tmp < min) min = tmp;
add(special.get(idx), i, needs);
}
return min;
}
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
this.price = price;
this.special = special;
int[] need = new int[needs.size()];
for (int i = 0; i < need.length; i++) {
need[i] = needs.get(i);
}
return buy(0, need);
}
}
大概看了一眼, 我感觉其实这个还是一个很普通的backtracking, 只不过他加了一个pruning, 也就是对于一个offer, 跟类似discussion最优解那样一样的思路, 限定这个offer最多能被take多少次; 这个pruning带来的优化按说应该是有限的, 因为这个pruning本身也需要一定的时间; 不过最后速度这么快也是有点神奇. 其实快的也不是很多就是了;
Problem 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.
Difficulty:Medium
Total Accepted:8.5K
Total Submissions:19.1K
Contributor:ckcz123
Companies
google
Related Topics
dynamic programmingdepth-first search