package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 638. 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.
 */
public class _638 {
    /**reference: https://leetcode.com/articles/shopping-offers/#approach-1-using-recursion-accepted*/
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return shopping(price, special, needs, 0);
    }

    public int shopping(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int i) {
        if (i == special.size()) {
            return dot(needs, price);
        }
        ArrayList<Integer> clone = new ArrayList(needs);
        int j = 0;
        for (j = 0; j < special.get(i).size() - 1; j++) {
            int diff = clone.get(j) - special.get(i).get(j);
            if (diff < 0) {
                break;
            }
            clone.set(j, diff);
        }
        if (j == special.get(i).size() - 1) {
            return Math.min(special.get(i).get(j) + shopping(price, special, clone, i), shopping(price, special, needs, i + 1));
        } else {
            return shopping(price, special, needs, i + 1);
        }
    }

    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;
    }
}

@@ -1853,19 +1853,71 @@
 8 %7B%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 referenc
@@ -2001,19 +2001,33 @@
 accepted
-*/%0A
+%0A         */%0A    
     publ
@@ -2121,32 +2121,36 @@
 eeds) %7B%0A        
+   
+ 
 return shopping(
@@ -2176,27 +2176,35 @@
 ds, 0);%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     public i
@@ -2299,24 +2299,28 @@
 ) %7B%0A        
+   
+ 
 if (i == spe
@@ -2330,24 +2330,28 @@
 l.size()) %7B%0A
+    
             
@@ -2384,26 +2384,32 @@
         
-%7D%0A
+    %7D%0A  
         
 ArrayLis
@@ -2400,16 +2400,18 @@
         
+  
 ArrayLis
@@ -2451,16 +2451,20 @@
 needs);%0A
+    
         
@@ -2478,24 +2478,28 @@
  0;%0A        
+    
 for (j = 0; 
@@ -2544,24 +2544,28 @@
             
+  
+  
 int diff = c
@@ -2609,24 +2609,28 @@
             
+    
 if (diff %3C 0
@@ -2649,16 +2649,20 @@
         
+    
 break;%0A 
@@ -2664,34 +2664,42 @@
 ak;%0A            
+ 
-%7D%0A
+   %7D%0A    
             clon
@@ -2714,34 +2714,42 @@
  diff);%0A        
+   
+ 
 %7D%0A
+    
         if (j ==
@@ -2774,24 +2774,28 @@
 ze() - 1) %7B%0A
+    
             
@@ -2911,16 +2911,20 @@
  + 1));%0A
+    
         
@@ -2936,32 +2936,36 @@
 e %7B%0A            
+    
 return shopping(
@@ -3007,17 +3007,29 @@
     
-%7D%0A
+    %7D%0A    
     %7D%0A%0A
+    
     
@@ -3083,24 +3083,28 @@
 ) %7B%0A        
+    
 int sum = 0;
@@ -3108,24 +3108,28 @@
  0;%0A        
+   
+ 
 for (int i =
@@ -3165,16 +3165,20 @@
         
+    
 sum += a
@@ -3205,26 +3205,33 @@
         
+ 
-%7D%0A
+   %7D%0A   
         
 return s
@@ -3214,32 +3214,33 @@
    %7D%0A           
+ 
 return sum;%0A    
@@ -3235,16 +3235,26 @@
 rn sum;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 638