Problem Description

Given an array cost[] of positive integers of size N and an integer W, cost[i] represents the cost of ‘i’ kg packet of oranges, the task is to find the minimum cost to buy W kgs of oranges. If it is not possible to buy exactly W kg oranges then the output will be -1

**Note:**1. cost[i] = -1 means that ‘i’ kg packet of orange is unavailable2. It may be assumed that there is infinite supply of all available packet types.

Example 1:

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

Problem Link

Minimum cost to fill given weight in a bag | Practice | GeeksforGeeks

Approach

This problem is similar to classical Unbounded Knapsack problem only the base conditions will differ

int minimumCost(int cost[], int N, int W) 
	{ 
        vector <int> wt,val;
        
        //prepare a wt and val vector
        for(int i=0;i<N;i++)
        {
            if(cost[i]!=-1)
            {
                wt.push_back(i+1);
                val.push_back(cost[i]);
            }
        }
        int n = val.size();
       
        int dp[n+1][W+1];
        
        //Initialize first row as INF
				for(int i=0;i<=W;i++)
        dp[0][i] = 999999999;
        
        //Initialize first column as 0
				for(int i=1;i<=n;i++)
        dp[i][0] = 0;
        
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=W;j++)
            {
                if(j>=wt[i-1])
                {
                                             
                    dp[i][j] = min(val[i-1] + dp**[i]**[j-wt[i-1]], dp[i-1][j]);
                }
                else
                dp[i][j] = dp[i-1][j];
                
            }
        }
        return dp[n][W]==999999999 ? -1 : dp[n][W];
        
	}