Minimum Cost To Fill Given Weight In Bag | Top Down➡️Bottom Up | 🔥4 Solutions🔥 | DP😋
vHiren
509
Dynamic ProgrammingCareer

Given an array cost[] of positive integers of size N and an integer "weight", cost[i] represents the cost of ith kg packet of oranges, the task is to find the minimum cost to buy "weight" kgs of oranges. If it is not possible to buy exactly "weight" kgs of oranges then output -1. Note :-
***1. cost[i] ≠ 0

  1. cost[i] = -1 means that the ith kg packet of orange is unavailable.
  2. It may be assumed that there is infinite supply of all available packet types.***

Input: N = 5
cost[] = {20, 10, 4, 50, 100}
Weight = 5
Output: 14
Explanation: Choose two oranges to minimize cost. First orange of 2Kg and cost 10. Second orange of 3Kg and cost 4.

Similiar To Unbounded Knapsack : https://leetcode.com/discuss/interview-question/4860416/unbounded-knapsack-top-downbottom-up-4-solutions-self-explanatory-c-code

Approach 1 : Using Top Down DP (Recursion To Memoization)

class Solution {
    int n;
    
    // O(2^(N+W)) & O(N+W)
    int solveWithoutMemo(const vector<int>& cost, int pos, int w) {
        if(w == 0)
            return 0;
            
        if(pos > n)
            return INT_MAX;
        
        int currSkip = solveWithoutMemo(cost, pos + 1, w);
        int currTake = INT_MAX;
    
        if(cost[pos - 1] != -1 && pos <= w) {
            currTake = solveWithoutMemo(cost, pos, w - pos);
            if(currTake != INT_MAX) currTake += cost[pos - 1];
        }
        
        return min(currSkip, currTake);
    }
    
    // O(N*W) & O(N*W)
    int solveWithMemo(vector<vector<int>>& dp, const vector<int>& cost, int pos, int w) {
        if(w == 0)
            return 0;
            
        if(pos > n)
            return INT_MAX;

        if(dp[pos][w] != -1)
            return dp[pos][w];
        
        int currSkip = solveWithMemo(dp, cost, pos + 1, w);
        int currTake = INT_MAX;
    
        if(cost[pos - 1] != -1 && pos <= w) {
            currTake = solveWithMemo(dp, cost, pos, w - pos);
            if(currTake != INT_MAX) currTake += cost[pos - 1];
        }
        
        return dp[pos][w] = min(currSkip, currTake);
    }

    // O(N*N*W) & O(N*W)
    int solveWithMemoLoop(vector<vector<int>>& dp, const vector<int>& cost, int start, int w) {
        if(w == 0)
            return 0;
            
        if(start > n)
            return INT_MAX;

        if(dp[start][w] != -1)
            return dp[start][w];
        
        int minCost = INT_MAX;

        for(int pos = start; pos <= n; ++pos) {
            int currTake = INT_MAX;

            if(cost[pos - 1] != -1 && pos <= w) {
                currTake = solveWithMemoLoop(dp, cost, pos, w - pos);
                if(currTake != INT_MAX) currTake += cost[pos - 1];
            }

            minCost = min(minCost, currTake);
        }
        
        return dp[start][w] = minCost;
    }
    
public:
    int minimumCost(int size, int w, vector<int>& cost) {
        n = size;
        vector<vector<int>> dp(n + 1, vector<int>(w + 1, -1));
        int ans = solveWithMemo(dp, cost, 1, w);
        return (ans == INT_MAX) ? -1 : ans;
    }
};

Approach 2 : Using Bottom Up (2D + 1D Tabulation)

class BottomUp {
    int n;
    
    // O(N*GW) & O(N*GW) : Where GW = given_w
    int solveBy2DTable(const vector<int>& cost, int given_w) {
        vector<vector<int>> dp(n + 1, vector<int>(given_w + 1, -1));
        
        for(int pos = 0; pos <= n; ++pos)
            dp[pos][0] = 0;
        
        for(int pos = n; pos >= 1; --pos) {
            for(int w = 1; w <= given_w; ++w) {
                int currSkip = (pos + 1 > n) ? INT_MAX : dp[pos + 1][w];
                int currTake = INT_MAX;
            
                if(cost[pos - 1] != -1 && pos <= w) {
                    currTake = dp[pos][w - pos];
                    if(currTake != INT_MAX) currTake += cost[pos - 1];
                }
                
                dp[pos][w] = min(currSkip, currTake);
            }
        }
        
        int ans = dp[1][given_w];
        return (ans == INT_MAX) ? -1 : ans;
    }
    
    // O(N*GW) & O(N*GW) : Where GW = given_w
    int solveBy2DEnhanced(const vector<int>& cost, int given_w) {
        vector<vector<int>> dp(n + 1, vector<int>(given_w + 1, 0));
        
        for(int pos = n; pos >= 1; --pos) {
            for(int w = 1; w <= given_w; ++w) {
                int currSkip = (pos + 1 > n) ? INT_MAX : dp[pos + 1][w];
                int currTake = INT_MAX;
            
                if(cost[pos - 1] != -1 && pos <= w) {
                    currTake = dp[pos][w - pos];
                    if(currTake != INT_MAX) currTake += cost[pos - 1];
                }
                
                dp[pos][w] = min(currSkip, currTake);
            }
        }
        
        int ans = dp[1][given_w];
        return (ans == INT_MAX) ? -1 : ans;
    }
    
    // O(N*GW) & O(GW) : Where GW = given_w
    int solveBy1DTable(const vector<int>& cost, int given_w) {
        vector<int> nextRow(given_w + 1, 0); // pos + 1
        
        for(int pos = n; pos >= 1; --pos) {
            vector<int> idealRow(given_w + 1, 0); // pos
            
            for(int w = 1; w <= given_w; ++w) {
                int currSkip = (pos + 1 > n) ? INT_MAX : nextRow[w];
                int currTake = INT_MAX;
            
                if(cost[pos - 1] != -1 && pos <= w) {
                    currTake = idealRow[w - pos];
                    if(currTake != INT_MAX) currTake += cost[pos - 1];
                }
                
                idealRow[w] = min(currSkip, currTake);
            }
            
            swap(nextRow, idealRow);
        }
        
        int ans = nextRow[given_w];
        return (ans == INT_MAX) ? -1 : ans;
    }
    
public:
    int minimumCost(int size, int w, vector<int>& cost) {
        n = size;
        return solveBy1DTable(cost, w);
    }
};

𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍

Note: This solutions are created by myself :)

Comments (6)