Minimum cost to fill given weight in a bag

23 August 2024

0

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>

Output

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>

Output

Time Complexity: O(N²)
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>

Output

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!

Minimum cost to fill given weight in a bag

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Java Program for Longest Common Subsequence

Maximum height of Tree when any Node can be considered as Root

Print Fibonacci sequence using 2 variables

LEAVE A REPLY Cancel reply

Most Popular

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

This is my surprise phone of the year [Video]

Recent Comments

EDITOR PICKS

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

POPULAR POSTS

Sticky Password vs. LastPass 2024: Which Is Better? by Katarina Glamoslija

Galaxy S25 on-device AI capability expands, reducing reliance on the cloud

OnePlus 13R launches with a huge battery upgrade, starting in China

POPULAR CATEGORY

ABOUT US

FOLLOW US