Problem Statement
You are given:
A bag that must be filled with exactly W kg of oranges.
An array
cost[]where:cost[i]represents the cost of a packet weighing(i + 1)kg.cost[i] = -1means that packet size is unavailable.
There is an infinite supply of every available packet.
Your task is to find the minimum cost required to buy exactly W kg of oranges.
If it is impossible to obtain exactly W kg, return -1.
Example
cost[] = {20, 10, 4, 50, 100}
W = 5
Possible combinations:
5 kg packet → Cost = 100
1 kg + 4 kg → Cost = 20 + 50 = 70
2 kg + 3 kg → Cost = 10 + 4 = 14
Minimum cost = 14
Observations
Notice that:
Every packet can be used multiple times.
We need to achieve an exact target weight.
We want the minimum cost among all valid combinations.
This is very similar to the Unbounded Knapsack Problem.
Why Unbounded Knapsack?
In a normal knapsack, each item can be selected only once.
Here:
A packet of 2 kg can be purchased multiple times.
A packet of 3 kg can be purchased multiple times.
Since items can be reused infinitely, this becomes an Unbounded Knapsack problem.
Dynamic Programming Approach
Let:
dp[j]
represent the minimum cost required to obtain exactly j kg.
Base Case
dp[0] = 0
Because zero weight requires zero cost.
For all other weights:
dp[j] = INF
which means currently unreachable.
State Transition
Suppose we have a packet:
weight = i + 1
price = cost[i]
If we want to form weight j:
j = (j - weight) + weight
Then:
dp[j] =
min(
dp[j],
dp[j - weight] + price
)
Explanation:
First make
(j - weight)kg.Add the current packet.
Compare with the existing answer.
DP Table Visualization
Example:
cost = [20,10,4,50,100]
W = 5
Initial:
Weight : 0 1 2 3 4 5
DP : 0 INF INF INF INF INF
Using 1 kg packet (Cost = 20):
0 20 40 60 80 100
Using 2 kg packet (Cost = 10):
0 20 10 30 20 40

Join the conversation! Your thoughts help the community grow.