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 1000000using namespace std;// cost[] initial cost array including unavailable packet// W capacity of bagint 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 caseint 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 bagimport 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 packetsINF = 1000000# cost[] initial cost array including unavailable packet# W capacity of bagdef 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 casecost = [1, 2, 3, 4, 5]W = 5n = 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 bagfunction 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> |
Output
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 packetsimport 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 packetsimport 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 codecost = [ 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 packetsusing 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> |
Output
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 packetsimport 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 packetsimport sysdef 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 packetsusing 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 packetsfunction 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> |
Output
14
Time Complexity: O(N*W)
Auxiliary Space: O(N*W)
This article is contributed by Shashank Mishra ( Gullu ).This article is reviewed by team GeeksForGeeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
