Home » Interview coding problems/challenges

Minimum cost to fill given weight in a bag

Minimum cost to fill given weight in a bag: Here, we are going to learn about a standard dynamic programming problem which has been featured in Amazon, Microsoft.
Submitted by Radib Kar, on June 14, 2020

Problem statement

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

Input

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains integers N and W where N denotes the size of array cost[ ] and W is the size of the bag.

The second line of each test case contains N space separated integers denoting elements of the array cost[ ].

Output

Print the minimum cost to buy exactly W kg oranges. If no such answer exists print "-1".

Constraints:

1 <= T <= 100
1 <= N, W <= 1000
1 <= cost[] <= 1000 

Example

Input:
2
5 5
20 10 4 50 100
6 5
-1 -1 4 5 -1 -1

Output:
14
-1

Explanation

So, for the first test case,
The 1 kg orange packet costs: 20
The 2 kg orange packet costs: 10
The 3 kg orange packet costs: 4
The 4 kg orange packet costs: 50
The 5 kg orange packet costs: 100

We need total of 5 Kg orange

So, there are many options to pick orange packets
Like picking five 1 kg packets costing 100
two 2 kg and one 1kg packet costing 40
one 2kg and one 3kg packet costing 14
one 1kg and one 4kg costing 70
one 5kg costing 100
so minimum cost one would be one 2kg and 
one 3kg bag combination which costs 14


For the second test case,
There is no possible combination to sum total 5kg oranges
Since, only available weight packets are of 3kg and 4kg
We can't take fractional parts
So, it's not possible and answer is -1.

Solution Approach

This is kind of a duplicate knapsack problem with some constraints. Here we need to keep the check for available packets too.

For example,

Say we have total weights 8

kg and for an instance, we are checking with packet weight 5

In such a case, we need to check to things.

1. Whether the 5kg packet is available or not.
2. Whether the sub-problem of size (8-5) kg is already solved or not.

If both satisfies then only we can proceed with this instance to compute the current problem.

The above concepts lead to the recurring formula which can be easily converted to Dynamic Programming like below,

1. Initialize dp[w+1] with INT_MAX where w is the total weight which is to be computed;
2. Set dp[0]=0 as base case,

3. for(int i=1;i<=w;i++)
       for(int j=0;j<n;j++)
           if ( a[j]  is availble  && (j+1)<=i && dp[i-(j+1)]  is already computed && dp[i-(j+1)]+a[j]<dp[i])
               dp[i]=dp[i-(j+1)]+a[j];
           end if
       end for
   end for
   

4. if(dp[w]  is not computed over the process,contains still the initial value)
       return -1;
   else dp[w] is the minimum cost
   

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int minimumCost(vector<int> a, int n, int w)
{
    int dp[w + 1];
    dp[0] = 0;
    for (int i = 1; i <= w; i++)
        dp[i] = INT_MAX;
    for (int i = 1; i <= w; i++) {
        for (int j = 0; j < n; j++) {
            if (a[j] != -1 && (j + 1) <= i && dp[i - (j + 1)] != INT_MAX && dp[i - (j + 1)] + a[j] < dp[i]) {
                dp[i] = dp[i - (j + 1)] + a[j];
            }
        }
    }

    if (dp[w] == INT_MAX)
        return -1;

    return dp[w];
}

int main()
{
    int t, n, item, w;

    cout << "Enter number of test cases\n";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Enter number of elements\n";
        cin >> n;

        cout << "Enter total weight\n";
        cin >> w;

        cout << "Enter the cost of weights, -1 if not available\n";
        vector<int> a;
        for (int j = 0; j < n; j++) {
            scanf("%d", &item);
            a.push_back(item);
        }

        cout << "minimum cost is: " << minimumCost(a, n, w) << endl;
    }

    return 0;
}

Output

Enter number of test cases
2
Enter number of elements
5 
Enter total weight
5
Enter the cost of weights, -1 if not available
20 10 4 50 100
minimum cost is: 14
Enter number of elements
6
Enter total weight
5
Enter the cost of weights, -1 if not available
-1 -1 4 5 -1 -1
minimum cost is: -1