Minimum cost to fill given weight in a bag

Problem Statement

You are given a bag of capacity W kg and n items with given weights and costs. Each item is available in packets of weight i+1 kg with cost cost[i]. If cost is -1, that packet is unavailable. Find the minimum cost to fill the bag exactly to weight W. If it's not possible, return -1.

Example:

• Input: cost = [1, 2, 3, 4, 5], W = 5
• Output: 5 (Buy 5 packets of 1 kg each at cost 1 each = 5, or 1 packet of 5 kg at cost 5)

Noob-Friendly Explanation

Imagine you have a shopping bag that must hold exactly W kilograms of rice. The store sells rice in different packet sizes: 1 kg, 2 kg, 3 kg, etc. Each packet size has a different price (some sizes might not be available). You can buy as many packets of any size as you want. You need to fill your bag to exactly W kg while spending the least money.

Approach 1: Brute Force

Intuition

Try all possible combinations of packets. For each packet size, decide how many to buy. Recursively explore all possibilities and find the minimum cost that fills the bag exactly.

Algorithm

1. Start with target weight W.
2. For each available packet size, try using it and recursively solve for the remaining weight.
3. Return the minimum cost among all choices.

class Solution {
    public static int minCostBrute(int[] cost, int W) {
        if (W == 0) return 0;
        if (W < 0) return -1;

        int minCost = Integer.MAX_VALUE;

        for (int i = 0; i < cost.length; i++) {
            int packetWeight = i + 1;
            if (cost[i] != -1 && packetWeight <= W) {
                int subResult = minCostBrute(cost, W - packetWeight);
                if (subResult != -1) {
                    minCost = Math.min(minCost, cost[i] + subResult);
                }
            }
        }

        return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
    }

    public static void main(String[] args) {
        int[] cost = {1, 2, 3, 4, 5};
        int W = 5;
        System.out.println(minCostBrute(cost, W)); // Output: 5
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - exponential due to repeated subproblems
• Space Complexity: O(W) - recursion stack depth

Approach 2: Optimal

Intuition

Use a 1D DP array where dp[w] represents the minimum cost to fill exactly w kg. For each weight from 1 to W, try all available packet sizes and pick the cheapest option.

Algorithm

1. Create a dp array of size W + 1, initialized to infinity (except dp[0] = 0).
2. For each weight w from 1 to W, for each packet size i+1 with cost cost[i] (if available), update: dp[w] = min(dp[w], dp[w - (i+1)] + cost[i]).
3. Return dp[W] if it's not infinity, else return -1.

class Solution {
    public static int minCostToFill(int[] cost, int W) {
        int n = cost.length;
        int[] dp = new int[W + 1];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int w = 1; w <= W; w++) {
            for (int i = 0; i < n; i++) {
                int packetWeight = i + 1;
                if (cost[i] != -1 && packetWeight <= w && dp[w - packetWeight] != Integer.MAX_VALUE) {
                    dp[w] = Math.min(dp[w], dp[w - packetWeight] + cost[i]);
                }
            }
        }

        return (dp[W] == Integer.MAX_VALUE) ? -1 : dp[W];
    }

    public static void main(String[] args) {
        int[] cost = {1, 2, 3, 4, 5};
        int W = 5;
        System.out.println(minCostToFill(cost, W)); // Output: 5
    }
}

Complexity Analysis

• Time Complexity: O(n * W) - two nested loops
• Space Complexity: O(W) - the dp array (can be optimized to O(W) from O(n*W))