Minimum Cost to Fill Given Weight

Time: O(w^2)

Space: O(w)

Problem Overview

Each cost[i] gives the price of buying weight i+1 directly.

Intuition

Each cost[i] gives the price of buying weight i+1 directly. To fill exactly weight w, either buy one available package or combine two smaller achievable weights. This is a shortest-path style DP over weights: once the minimum cost for x and y is known, weight x + y can be improved by paying mem[x] + mem[y].

Algorithm

1Create mem[1..w], initialized to -1 for unreachable weights.
2For each weight x from 1 to w, if cost[x-1] exists, set mem[x] = min(mem[x], cost[x-1]).
3For every pair 1 <= x <= y with x + y <= w, if mem[x] and mem[y] are reachable, relax mem[x + y].
4Use mem[x + y] = min(mem[x + y], mem[x] + mem[y]).
5Return mem[w]; -1 means weight w cannot be formed.

Example Walkthrough

Input: cost = [1, 2, 4], w = 5

1. Direct costs: weight 1 costs 1, weight 2 costs 2, weight 3 costs 4.
2. Weight 4 is best formed as 2 + 2 with cost 2 + 2 = 4.
3. Weight 5 is best formed as 2 + 3 with cost 2 + 4 = 6, or 1 + 4 with cost 1 + 4 = 5.
4. Minimum cost to reach weight 5 is 5.

Output: 5

Common Pitfalls

• Treat -1 as unreachable; never add two unreachable subweights.
• cost[i] corresponds to weight i + 1, not weight i.
• Check all pairs x <= y so combinations like 2 + 3 and 3 + 2 are not double-counted incorrectly.

Minimum Cost to Fill Given Weight.java

Java

// Approach: DP where mem[x] is the minimum cost to reach weight x. Seed from direct item
// costs, then relax mem[x + y] = min(mem[x + y], mem[x] + mem[y]) for all valid pairs.
// Time: O(w^2) Space: O(w)

class Solution {

    public int minimumCost(int[] cost, int w) {
        int size = cost.length;
        int mem[] = new int[w + 1];

        /*
        * Let's initialize, if such cost is available
        * we use it otherwise we fallback to -1
         */
        for (int x = 1; x <= w; x++) {
            int c = x - 1 < size ? cost[x - 1] : -1;
            mem[x] = max(c, -1);
        }

        /*
         * Combine previously computed weights to discover cheaper
         * ways of obtaining larger weights.
         *
         * mem[x + y] = min(mem[x + y], mem[x] + mem[y])
         */
        for (int x = 1; x < w; x++) {
            for (int y = x; y < w - x + 1; y++) {
                if (mem[x] == -1 || mem[y] == -1) {
                    continue;
                }
                mem[y + x] = min(mem[y + x], mem[x] + mem[y]);
            }
        }

        return mem[w];
    }

    int max(int a, int b) {
        return a > b ? a : b;
    }

    int min(int a, int b) {
        if (a == -1 || b == -1) {
            return max(a, b);
        }
        return a < b ? a : b;
    }
}

Was this solution helpful?