Tutorialspoint.dev

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 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 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.


This problem is can be reduced to 0-1 Knapsack Problem. So in 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 cost of ‘i’ kg packet of orange and wt[] for storing weight of corresponding packet. Suppose cost[i] = 50 so weight of packet will be i and 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 maximum capacity of bag.
  • Initialize 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 make weight W by using these weights else output will be min_cost[n][W].

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 then 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 then 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.

Python 3

# 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 then 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 then 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
?>


Output:

5


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter