Minimum Cost to Fill Given Weight (Dynamic Programming)

Sandhiya Priya
18h
90
0
1

100

Article

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] = -1 means 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

Using 3 kg packet (Cost = 4):

0 20 10 4 20 14

Final answer:

dp[5] = 14

Why Does the Inner Loop Start From Weight?

For a packet of size weight:

for(int j = weight; j <= W; j++)

We cannot form weights smaller than the packet itself.

For example:

Packet = 3kg

It cannot contribute to:

dp[1]
dp[2]

Hence we start from 3.

Complete Java Solution

class Solution {
    public int minimumCost(int[] cost, int w) {

        int n = cost.length;
        int INF = (int)1e9;

        int[] dp = new int[w + 1];

        for(int i = 1; i <= w; i++) {
            dp[i] = INF;
        }

        dp[0] = 0;

        for(int i = 0; i < n; i++) {

            if(cost[i] == -1)
                continue;

            int weight = i + 1;
            int price = cost[i];

            for(int j = weight; j <= w; j++) {

                if(dp[j - weight] != INF) {

                    dp[j] = Math.min(
                        dp[j],
                        dp[j - weight] + price
                    );
                }
            }
        }

        return dp[w] == INF ? -1 : dp[w];
    }
}

Complexity Analysis

Let:

n = cost.length
W = target weight

Time Complexity

O(n × W)

Because:

We iterate through every packet.
For each packet, we traverse all possible weights.

Space Complexity

O(W)

Only a one-dimensional DP array is used.

Interview Discussion

How to Identify This Problem?

Look for these clues:

Minimum/Maximum value required.
Exact target weight.
Infinite supply of items.
Repeated usage allowed.

These keywords usually indicate:

Unbounded Knapsack

Key Takeaway

The problem can be transformed into:

Find the minimum cost to reach an exact weight using unlimited packets.

This is a classic Unbounded Knapsack DP where:

dp[j] = min(dp[j], dp[j - weight] + cost)

Using a 1D DP array reduces space complexity from O(n × W) to O(W) while maintaining the optimal O(n × W) time complexity.

Summary

To solve the minimum cost orange packets problem, model it as an Unbounded Knapsack problem where each packet size can be used infinitely many times. Use a one-dimensional DP array where dp[j] stores the minimum cost to achieve exactly j kg. For every available packet, update the DP table using the transition dp[j] = min(dp[j], dp[j - weight] + cost). This approach efficiently finds the minimum cost in O(n × W) time and O(W) space while correctly handling unavailable packet sizes and exact-weight requirements.