Minimum cost to fill given weight in a bag
You are given a bag of size W kg and you are provided costs of packets different weights of oranges in array cost[] where cost[i] is basically the cost of ‘i’ kg packet of oranges. Where cost[i] = -1 means that ‘i’ kg packet of orange is unavailable
Find the minimum total cost to buy exactly W kg oranges and if it is not possible to buy exactly W kg oranges then print -1. It may be assumed that there is an infinite supply of all available packet types.
Note: array starts from index 1.
Examples:
Input : W = 5, cost[] = {20, 10, 4, 50, 100} Output : 14 We can choose two oranges to minimize cost. First orange of 2Kg and cost 10. Second orange of 3Kg and cost 4. Input : W = 5, cost[] = {1, 10, 4, 50, 100} Output : 5 We can choose five oranges of weight 1 kg. Input : W = 5, cost[] = {1, 2, 3, 4, 5} Output : 5 Costs of 1, 2, 3, 4 and 5 kg packets are 1, 2, 3, 4 and 5 Rs respectively. We choose packet of 5kg having cost 5 for minimum cost to get 5Kg oranges. Input : W = 5, cost[] = {-1, -1, 4, 5, -1} Output : -1 Packets of size 1, 2 and 5 kg are unavailable because they have cost -1. Cost of 3 kg packet is 4 Rs and of 4 kg is 5 Rs. Here we have only weights 3 and 4 so by using these two we can not make exactly W kg weight, therefore answer is -1.
Method 1:
This problem is can be reduced to Unbounded Knapsack. So in the cost array, we first ignore those packets which are not available i.e; cost is -1 and then traverse the cost array and create two array val[] for storing the cost of ‘i’ kg packet of orange and wt[] for storing weight of the corresponding packet. Suppose cost[i] = 50 so the weight of the packet will be i and the cost will be 50.
Algorithm :
- Create matrix min_cost[n+1][W+1], where n is number of distinct weighted packets of orange and W is the maximum capacity of the bag.
- Initialize the 0th row with INF (infinity) and 0th Column with 0.
- Now fill the matrix
- if wt[i-1] > j then min_cost[i][j] = min_cost[i-1][j] ;
- if wt[i-1] <= j then min_cost[i][j] = min(min_cost[i-1][j], val[i-1] + min_cost[i][j-wt[i-1]]);
- If min_cost[n][W]==INF then output will be -1 because this means that we cant not make weight W by using these weights else output will be min_cost[n][W].
Below is the implementation of the above algorithm:
C++
// C++ program to find minimum cost to get exactly // W Kg with given packets #include<bits/stdc++.h> #define INF 1000000 using namespace std; // cost[] initial cost array including unavailable packet // W capacity of bag int MinimumCost( int cost[], int n, int W) { // val[] and wt[] arrays // val[] array to store cost of 'i' kg packet of orange // wt[] array weight of packet of orange vector< int > val, wt; // traverse the original cost[] array and skip // unavailable packets and make val[] and wt[] // array. size variable tells the available number // of distinct weighted packets int size = 0; for ( int i=0; i<n; i++) { if (cost[i]!= -1) { val.push_back(cost[i]); wt.push_back(i+1); size++; } } n = size; int min_cost[n+1][W+1]; // fill 0th row with infinity for ( int i=0; i<=W; i++) min_cost[0][i] = INF; // fill 0'th column with 0 for ( int i=1; i<=n; i++) min_cost[i][0] = 0; // now check for each weight one by one and fill the // matrix according to the condition for ( int i=1; i<=n; i++) { for ( int j=1; j<=W; j++) { // wt[i-1]>j means capacity of bag is // less than weight of item if (wt[i-1] > j) min_cost[i][j] = min_cost[i-1][j]; // here we check we get minimum cost either // by including it or excluding it else min_cost[i][j] = min(min_cost[i-1][j], min_cost[i][j-wt[i-1]] + val[i-1]); } } // exactly weight W can not be made by given weights return (min_cost[n][W]==INF)? -1: min_cost[n][W]; } // Driver program to run the test case int main() { int cost[] = {1, 2, 3, 4, 5}, W = 5; int n = sizeof (cost)/ sizeof (cost[0]); cout << MinimumCost(cost, n, W); return 0; } |
Java
// Java Code for Minimum cost to // fill given weight in a bag import java.util.*; class GFG { // cost[] initial cost array including // unavailable packet W capacity of bag public static int MinimumCost( int cost[], int n, int W) { // val[] and wt[] arrays // val[] array to store cost of 'i' kg // packet of orange wt[] array weight of // packet of orange Vector<Integer> val = new Vector<Integer>(); Vector<Integer> wt = new Vector<Integer>(); // traverse the original cost[] array and skip // unavailable packets and make val[] and wt[] // array. size variable tells the available // number of distinct weighted packets int size = 0 ; for ( int i = 0 ; i < n; i++) { if (cost[i] != - 1 ) { val.add(cost[i]); wt.add(i + 1 ); size++; } } n = size; int min_cost[][] = new int [n+ 1 ][W+ 1 ]; // fill 0th row with infinity for ( int i = 0 ; i <= W; i++) min_cost[ 0 ][i] = Integer.MAX_VALUE; // fill 0'th column with 0 for ( int i = 1 ; i <= n; i++) min_cost[i][ 0 ] = 0 ; // now check for each weight one by one and // fill the matrix according to the condition for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= W; j++) { // wt[i-1]>j means capacity of bag is // less than weight of item if (wt.get(i- 1 ) > j) min_cost[i][j] = min_cost[i- 1 ][j]; // here we check we get minimum cost // either by including it or excluding // it else min_cost[i][j] = Math.min(min_cost[i- 1 ][j], min_cost[i][j-wt.get(i- 1 )] + val.get(i- 1 )); } } // exactly weight W can not be made by // given weights return (min_cost[n][W] == Integer.MAX_VALUE)? - 1 : min_cost[n][W]; } /* Driver program to test above function */ public static void main(String[] args) { int cost[] = { 1 , 2 , 3 , 4 , 5 }, W = 5 ; int n = cost.length; System.out.println(MinimumCost(cost, n, W)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python program to find minimum cost to get exactly # W Kg with given packets INF = 1000000 # cost[] initial cost array including unavailable packet # W capacity of bag def MinimumCost(cost, n, W): # val[] and wt[] arrays # val[] array to store cost of 'i' kg packet of orange # wt[] array weight of packet of orange val = list () wt = list () # traverse the original cost[] array and skip # unavailable packets and make val[] and wt[] # array. size variable tells the available number # of distinct weighted packets. size = 0 for i in range (n): if (cost[i] ! = - 1 ): val.append(cost[i]) wt.append(i + 1 ) size + = 1 n = size min_cost = [[ 0 for i in range (W + 1 )] for j in range (n + 1 )] # fill 0th row with infinity for i in range (W + 1 ): min_cost[ 0 ][i] = INF # fill 0th column with 0 for i in range ( 1 , n + 1 ): min_cost[i][ 0 ] = 0 # now check for each weight one by one and fill the # matrix according to the condition for i in range ( 1 , n + 1 ): for j in range ( 1 , W + 1 ): # wt[i-1]>j means capacity of bag is # less than weight of item if (wt[i - 1 ] > j): min_cost[i][j] = min_cost[i - 1 ][j] # here we check we get minimum cost either # by including it or excluding it else : min_cost[i][j] = min (min_cost[i - 1 ][j], min_cost[i][j - wt[i - 1 ]] + val[i - 1 ]) # exactly weight W can not be made by given weights if (min_cost[n][W] = = INF): return - 1 else : return min_cost[n][W] # Driver program to run the test case cost = [ 1 , 2 , 3 , 4 , 5 ] W = 5 n = len (cost) print (MinimumCost(cost, n, W)) # This code is contributed by Soumen Ghosh. |
C#
// C# Code for Minimum cost to // fill given weight in a bag using System; using System.Collections.Generic; class GFG { // cost[] initial cost array including // unavailable packet W capacity of bag public static int MinimumCost( int []cost, int n, int W) { // val[] and wt[] arrays // val[] array to store cost of 'i' kg // packet of orange wt[] array weight of // packet of orange List< int > val = new List< int >(); List< int > wt = new List< int >(); // traverse the original cost[] array and skip // unavailable packets and make val[] and wt[] // array. size variable tells the available // number of distinct weighted packets int size = 0; for ( int i = 0; i < n; i++) { if (cost[i] != -1) { val.Add(cost[i]); wt.Add(i + 1); size++; } } n = size; int [,]min_cost = new int [n+1,W+1]; // fill 0th row with infinity for ( int i = 0; i <= W; i++) min_cost[0,i] = int .MaxValue; // fill 0'th column with 0 for ( int i = 1; i <= n; i++) min_cost[i,0] = 0; // now check for each weight one by one and // fill the matrix according to the condition for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= W; j++) { // wt[i-1]>j means capacity of bag is // less than weight of item if (wt[i-1] > j) min_cost[i,j] = min_cost[i-1,j]; // here we check we get minimum cost // either by including it or excluding // it else min_cost[i,j] = Math.Min(min_cost[i-1,j], min_cost[i,j-wt[i-1]] + val[i-1]); } } // exactly weight W can not be made by // given weights return (min_cost[n,W] == int .MaxValue )? -1: min_cost[n,W]; } /* Driver program to test above function */ public static void Main() { int []cost = {1, 2, 3, 4, 5}; int W = 5; int n = cost.Length; Console.WriteLine(MinimumCost(cost, n, W)); } } // This code is contributed by Ryuga |
PHP
<?php // PHP program to find minimum cost to // get exactly W Kg with given packets $INF = 1000000; // cost[] initial cost array including // unavailable packet W capacity of bag function MinimumCost(& $cost , $n , $W ) { global $INF ; // val[] and wt[] arrays // val[] array to store cost of 'i' // kg packet of orange // wt[] array weight of packet of orange $val = array (); $wt = array (); // traverse the original cost[] array // and skip unavailable packets and // make val[] and wt[] array. size // variable tells the available number // of distinct weighted packets $size = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $cost [ $i ] != -1) { array_push ( $val , $cost [ $i ]); array_push ( $wt , $i + 1); $size ++; } } $n = $size ; $min_cost = array_fill (0, $n + 1, array_fill (0, $W + 1, NULL)); // fill 0th row with infinity for ( $i = 0; $i <= $W ; $i ++) $min_cost [0][ $i ] = $INF ; // fill 0'th column with 0 for ( $i = 1; $i <= $n ; $i ++) $min_cost [ $i ][0] = 0; // now check for each weight one by // one and fill the matrix according // to the condition for ( $i = 1; $i <= $n ; $i ++) { for ( $j = 1; $j <= $W ; $j ++) { // wt[i-1]>j means capacity of bag // is less than weight of item if ( $wt [ $i - 1] > $j ) $min_cost [ $i ][ $j ] = $min_cost [ $i - 1][ $j ]; // here we check we get minimum // cost either by including it // or excluding it else $min_cost [ $i ][ $j ] = min( $min_cost [ $i - 1][ $j ], $min_cost [ $i ][ $j - $wt [ $i - 1]] + $val [ $i - 1]); } } // exactly weight W can not be made // by given weights if ( $min_cost [ $n ][ $W ] == $INF ) return -1; else return $min_cost [ $n ][ $W ]; } // Driver Code $cost = array (1, 2, 3, 4, 5); $W = 5; $n = sizeof( $cost ); echo MinimumCost( $cost , $n , $W ); // This code is contributed by ita_c ?> |
Javascript
<script> // Javascript program to find minimum cost to get exactly // W Kg with given packets let INF = 1000000; // cost[] initial cost array including unavailable packet // W capacity of bag function MinimumCost(cost, n, W) { // val[] and wt[] arrays // val[] array to store cost of 'i' kg packet of orange // wt[] array weight of packet of orange let val = [], wt = []; // traverse the original cost[] array and skip // unavailable packets and make val[] and wt[] // array. size variable tells the available number // of distinct weighted packets let size = 0; for (let i=0; i<n; i++) { if (cost[i]!= -1) { val.push(cost[i]); wt.push(i+1); size++; } } n = size; let min_cost = new Array(n+1); for (let i = 0; i < n + 1; i++) { min_cost[i] = new Array(W + 1); } // fill 0th row with infinity for (let i=0; i<=W; i++) min_cost[0][i] = INF; // fill 0'th column with 0 for (let i=1; i<=n; i++) min_cost[i][0] = 0; // now check for each weight one by one and fill the // matrix according to the condition for (let i=1; i<=n; i++) { for (let j=1; j<=W; j++) { // wt[i-1]>j means capacity of bag is // less than weight of item if (wt[i-1] > j) min_cost[i][j] = min_cost[i-1][j]; // here we check we get minimum cost either // by including it or excluding it else min_cost[i][j] = Math.min(min_cost[i-1][j], min_cost[i][j-wt[i-1]] + val[i-1]); } } // exactly weight W can not be made by given weights return (min_cost[n][W]==INF)? -1: min_cost[n][W]; } // Driver code let cost = [1, 2, 3, 4, 5], W = 5; let n = cost.length; document.write(MinimumCost(cost, n, W)); // This code is contributed by suresh07. </script> |
5
Time Complexity: O(N*W)
Auxiliary Space: O(N*W)
Space Optimized Solution If we take a closer look at this problem, we may notice that this is a variation of Rod Cutting Problem. Instead of doing maximization, here we need to do minimization.
C++
// C++ program to find minimum cost to // get exactly W Kg with given packets #include<bits/stdc++.h> using namespace std; /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ int minCost( int cost[], int n) { int dp[n+1]; dp[0] = 0; // Build the table val[] in bottom up // manner and return the last entry // from the table for ( int i = 1; i<=n; i++) { int min_cost = INT_MAX; for ( int j = 0; j < i; j++) if (cost[j]!=-1) min_cost = min(min_cost, cost[j] + dp[i-j-1]); dp[i] = min_cost; } return dp[n]; } /* Driver code */ int main() { int cost[] = {20, 10, 4, 50, 100}; int W = sizeof (cost)/ sizeof (cost[0]); cout << minCost(cost, W); return 0; } |
Java
// Java program to find minimum cost to // get exactly W Kg with given packets import java.util.*; class Main { /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ public static int minCost( int cost[], int n) { int dp[] = new int [n + 1 ]; dp[ 0 ] = 0 ; // Build the table val[] in bottom up // manner and return the last entry // from the table for ( int i = 1 ; i <= n; i++) { int min_cost = Integer.MAX_VALUE; for ( int j = 0 ; j < i; j++) if (cost[j]!=- 1 ) { min_cost = Math.min(min_cost, cost[j] + dp[i - j - 1 ]); } dp[i] = min_cost; } return dp[n]; } public static void main(String[] args) { int cost[] = { 10 ,- 1 ,- 1 ,- 1 ,- 1 }; int W = cost.length; System.out.print(minCost(cost, W)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to find minimum cost to # get exactly W Kg with given packets import sys # Returns the best obtainable price for # a rod of length n and price[] as prices # of different pieces def minCost(cost, n): dp = [ 0 for i in range (n + 1 )] # Build the table val[] in bottom up # manner and return the last entry # from the table for i in range ( 1 , n + 1 ): min_cost = sys.maxsize for j in range (i): if cost[j]! = - 1 : min_cost = min (min_cost, cost[j] + dp[i - j - 1 ]) dp[i] = min_cost return dp[n] # Driver code cost = [ 10 , - 1 , - 1 , - 1 , - 1 ] W = len (cost) print (minCost(cost, W)) # This code is contributed by rag2127 |
C#
// C# program to find minimum cost to // get exactly W Kg with given packets using System; class GFG { /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ static int minCost( int [] cost, int n) { int [] dp = new int [n + 1]; dp[0] = 0; // Build the table val[] in bottom up // manner and return the last entry // from the table for ( int i = 1; i <= n; i++) { int min_cost = Int32.MaxValue; for ( int j = 0; j < i; j++) if (cost[j]!=-1) min_cost = Math.Min(min_cost, cost[j] + dp[i - j - 1]); dp[i] = min_cost; } return dp[n]; } // Driver code static void Main() { int [] cost = {20, 10, 4, 50, 100}; int W = cost.Length; Console.Write(minCost(cost, W)); } } // This code is contributed by divyesh072019 |
Javascript
<script> // Javascript program to find minimum cost to // get exactly W Kg with given packets /* Returns the best obtainable price for a rod of length n and price[] as prices of different pieces */ function minCost(cost, n) { let dp = new Array(n+1); dp[0] = 0; // Build the table val[] in bottom up // manner and return the last entry // from the table for (let i = 1; i<=n; i++) { let min_cost = Number.MAX_VALUE; for (let j = 0; j < i; j++) if (j < n) min_cost = Math.min(min_cost, cost[j] + dp[i-j-1]); dp[i] = min_cost; } return dp[n]; } let cost = [20, 10, 4, 50, 100]; let W = cost.length; document.write(minCost(cost, W)); </script> |
14
Time Complexity: O(N2)
Auxiliary Space: O(N)
Top Down Approach: We can also solve the problem using memoization.
C++
// C++ program to find minimum cost to // get exactly W Kg with given packets #include <bits/stdc++.h> using namespace std; int helper(vector< int >& cost, vector< int >& weight, int n, int w, vector<vector< int > >& dp) { // base cases if (w == 0) return 0; if (w < 0 or n <= 0) return INT_MAX; if (dp[n][w] != -1) return dp[n][w]; if (cost[n - 1] < 0) return dp[n][w] = min(INT_MAX, helper(cost, weight, n - 1, w, dp)); if (weight[n - 1] <= w) { return dp[n][w] = min(cost[n - 1] + helper(cost, weight, n, w - weight[n - 1], dp), helper(cost, weight, n - 1, w, dp)); } return dp[n][w] = helper(cost, weight, n - 1, w, dp); } int minCost(vector< int >& cost, int W) { int N = cost.size(); // Your code goes here vector< int > weight(N); // create the weight array for ( int i = 1; i <= N; i++) { weight[i - 1] = i; } // initialize the dp array vector<vector< int > > dp(N + 1, vector< int >(W + 1, -1)); int res = helper(cost, weight, N, W, dp); // return -1 if result is MAX return (res == INT_MAX) ? -1 : res; } /* Driver code */ int main() { vector< int > cost = { 20, 10, 4, 50, 100 }; int W = cost.size(); cout << minCost(cost, W); return 0; } |
Java
// Java program to find minimum cost to // get exactly W Kg with given packets import java.io.*; class GFG { public static int helper( int cost[], int weight[], int n, int w, int dp[][]) { // base cases if (w == 0 ) return 0 ; if (w < 0 || n <= 0 ) return Integer.MAX_VALUE; if (dp[n][w] != - 1 ) return dp[n][w]; if (cost[n - 1 ] < 0 ) return dp[n][w] = Math.min( Integer.MAX_VALUE, helper(cost, weight, n - 1 , w, dp)); if (weight[n - 1 ] <= w) { return dp[n][w] = Math.min( cost[n - 1 ] + helper(cost, weight, n, w - weight[n - 1 ], dp), helper(cost, weight, n - 1 , w, dp)); } return dp[n][w] = helper(cost, weight, n - 1 , w, dp); } public static int minCost( int cost[], int W) { int N = cost.length; int weight[] = new int [N]; // create the weight array for ( int i = 1 ; i <= N; i++) { weight[i - 1 ] = i; } // initialize the dp array int dp[][] = new int [N + 1 ][W + 1 ]; for ( int i = 0 ; i < N + 1 ; i++) for ( int j = 0 ; j < W + 1 ; j++) dp[i][j] = - 1 ; int res = helper(cost, weight, N, W, dp); // return -1 if result is MAX return (res == Integer.MAX_VALUE) ? - 1 : res; } // Driver Code public static void main(String[] args) { int cost[] = { 20 , 10 , 4 , 50 , 100 }; int W = cost.length; System.out.print(minCost(cost, W)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python3 program to find minimum cost to # get exactly W Kg with given packets import sys def helper(cost, weight, n, w, dp): # base cases if (w = = 0 ): return 0 if (w < 0 or n < = 0 ): return sys.maxsize if (dp[n][w] ! = - 1 ): return dp[n][w] if (cost[n - 1 ] < 0 ): dp[n][w] = min (sys.maxsize, helper(cost, weight, n - 1 , w, dp)) return dp[n][w] if (weight[n - 1 ] < = w): dp[n][w] = min (cost[n - 1 ] + helper(cost, weight, n, w - weight[n - 1 ], dp), helper(cost, weight, n - 1 , w, dp)) return dp[n][w] dp[n][w] = helper(cost, weight, n - 1 , w, dp) return dp[n][w] def minCost(cost, W): N = len (cost) weight = [ 0 for i in range (N)] # create the weight array for i in range ( 1 ,N + 1 ): weight[i - 1 ] = i # initialize the dp array dp = [[ - 1 for i in range (W + 1 )] for j in range (N + 1 )] res = helper(cost, weight, N, W, dp) # return -1 if result is MAX return - 1 if (res = = sys.maxsize) else res # Driver code cost = [ 20 , 10 , 4 , 50 , 100 ] W = len (cost) print (minCost(cost, W)) # This code is contributed by shinjanpatra |
C#
// C# program to find minimum cost to // get exactly W Kg with given packets using System; class GFG { static int helper( int [] cost, int [] weight, int n, int w, int [,] dp) { // base cases if (w == 0) return 0; if (w < 0 || n <= 0) return Int32.MaxValue; if (dp[n,w] != -1) return dp[n,w]; if (cost[n - 1] < 0) return dp[n,w] = Math.Min( Int32.MaxValue, helper(cost, weight, n - 1, w, dp)); if (weight[n - 1] <= w) { return dp[n,w] = Math.Min( cost[n - 1] + helper(cost, weight, n, w - weight[n - 1], dp), helper(cost, weight, n - 1, w, dp)); } return dp[n,w] = helper(cost, weight, n - 1, w, dp); } static int minCost( int [] cost, int W) { int N = cost.Length; int [] weight = new int [N]; // create the weight array for ( int i = 1; i <= N; i++) { weight[i - 1] = i; } // initialize the dp array int [,] dp = new int [N + 1, W + 1]; for ( int i = 0; i < N + 1; i++) for ( int j = 0; j < W + 1; j++) dp[i,j] = -1; int res = helper(cost, weight, N, W, dp); // return -1 if result is MAX return (res == Int32.MaxValue) ? -1 : res; } // Driver Code static public void Main() { int [] cost = { 20, 10, 4, 50, 100 }; int W = cost.Length; Console.Write(minCost(cost, W)); } } // This code is contributed by kothavvsaakash |
Javascript
<script> // JavaScript program to find minimum cost to // get exactly W Kg with given packets function helper(cost, weight, n, w, dp) { // base cases if (w == 0) return 0; if (w < 0 || n <= 0) return Number.MAX_VALUE; if (dp[n][w] != -1) return dp[n][w]; if (cost[n - 1] < 0) return dp[n][w] = Math.min(Number.MAX_VALUE, helper(cost, weight, n - 1, w, dp)); if (weight[n - 1] <= w) { return dp[n][w] = Math.min(cost[n - 1] + helper(cost, weight, n, w - weight[n - 1], dp), helper(cost, weight, n - 1, w, dp)); } return dp[n][w] = helper(cost, weight, n - 1, w, dp); } function minCost(cost,W) { let N = cost.length; // Your code goes here let weight = new Array(N); // create the weight array for (let i = 1; i <= N; i++) { weight[i - 1] = i; } // initialize the dp array let dp = new Array(N + 1).fill(-1).map(()=> new Array(W + 1).fill(-1)); let res = helper(cost, weight, N, W, dp); // return -1 if result is MAX return (res == Number.MAX_VALUE) ? -1 : res; } /* Driver code */ let cost = [ 20, 10, 4, 50, 100 ]; let W = cost.length; document.write(minCost(cost, W), "</br>" ); // This code is contributed by shinjanpatra </script> |
14
Time Complexity: O(N*W)
Auxiliary Space: O(N*W)
This article is reviewed by team w3wiki.
Contact Us