DP with BFS, Naive Idea!


  • 0
    L

    The idea is very easy.

    Note:state is keyArr[] which represents the number of each item left to be bought.
    It is just like backpack problem, for each state, we need to check whether an offer is available, if it is available:

    1. The price of using this offer is less than not using it. Then we should implement this offer. Update the final result if needed. Update the state after using this offer in the map. Put the new state in the queue.
    2. The price of using this offer is not less than not using it. Discard it.

    The above process is BFS process.

    The DP part is to record the old value of each state which has already been calculated, just like memorization method.

    Since we need to overwrite equals function if we use array to be the key of map, I use encode and decode to record each state.

    The only implicit assumption is that for each state, if we can use an offer, then this offer must save money.

    Complexity: For this certain problem, the key point is the number of offers due to the limit of types and number of items.
    To fill in the map, the worst case is the multiplication of all numbers of items. For example, if we have 6 items and the number of each item is 6, then there are 6^6 blank to be filled in.
    The only part to use the number of offer is the DFS part, so the time complexity of the algorithm is approximately O(number of items) ^ x * O(number of offers). If we can neglect the number of items, it is O(n), where n is the number of offers.

    public class Solution {
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int n = price.size();
            if (n == 0) {
                return 0;
            }
            int[] keyArr = new int[n];
            HashMap<String, Integer> map = new HashMap<>();
            int sum = 0;
            for (int i = 0; i < needs.size(); i++) {
                keyArr[i] = needs.get(i);
                sum += price.get(i) * needs.get(i);
            }
            map.put(encode(keyArr), sum);
            Queue<String> q = new LinkedList<>();
            q.offer(encode(keyArr));
            
            int res = sum;
            while (q.size() > 0){
                int size = q.size();
                
                for (int i = 0; i < size; i++){
                    String key = q.poll();
                    for (List<Integer> offer : special){
                        keyArr = decode(key);
                        if (validOffer(keyArr, offer)){
                            
                            int currPrice = map.get(key) + offer.get(offer.size()-1);
                            for (int j = 0; j < keyArr.length; j++){
                                keyArr[j] -= offer.get(j);
                                currPrice -= offer.get(j) * price.get(j);
                            }
                            
                            String newKey = encode(keyArr);
                            int originalPrice = map.getOrDefault(newKey, Integer.MAX_VALUE);
    
                            if (originalPrice > currPrice){
                                map.put(newKey, currPrice);
                                res = Math.min(res, currPrice);
                                q.offer(newKey);
                            }
                        }
                    }
                }
            }
            
            return res;
        }
        
        private String encode(int[] keyArr) {
            StringBuilder key = new StringBuilder();
            
            for (int i : keyArr){
                key.append(i);
            }
            
            return key.toString();
        }
        
        private int[] decode(String key){
            int[] keyArr = new int[key.length()];
            
            for (int i = 0; i < key.length(); i++){
                keyArr[i] = key.charAt(i) - '0';
            }
            
            return keyArr;
        }
        
        private boolean validOffer(int[] keyArr, List<Integer> offer){
            for (int i = 0; i < keyArr.length; i++){
                if (offer.get(i) > keyArr[i]){
                    return false;
                }
            }
            
            return true;
        }
    }
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.