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.
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[ ].
Print the minimum cost to buy exactly W kg oranges. If no such answer exists print "-1".
1 <= T <= 100 1 <= N, W <= 1000 1 <= cost <= 1000
Input: 2 5 5 20 10 4 50 100 6 5 -1 -1 4 5 -1 -1 Output: 14 -1
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.
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,
Output:need an explanation for this answer? contact us directly to get an explanation for this answer