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. 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.
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.
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,
C++ Implementation:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer