318. Minimum Cost to Fill a Bag With Given Weight

You're given the cost of packets of weight 1, 2, ..., n (a cost of -1 means a packet of that weight isn't available), with an unlimited supply of every available weight. Find the minimum total cost of packets needed to fill a bag with exactly weight W. Print -1 if it's impossible.

Input: The first line contains an integer n. The second line contains n space-separated integers, the cost of a packet of weight 1 through n (-1 meaning that weight is unavailable). The third line contains the integer W, the target weight to fill. Output: Print a single integer - the minimum total cost to make exactly weight W, or -1 if it's impossible.

1 <= n <= 1000, 1 <= W <= 1000

Unreachable amounts must be tracked distinctly from a genuine cost of 0 - using a sentinel like infinity (rather than 0) for 'not yet reachable' is essential, or the algorithm could incorrectly treat an unreachable weight as free.

Find the minimum cost to fill a bag with exactly a target weight, using packets of various weights and costs (some weights unavailable), unlimited supply of each available weight. Brute force: Try every possible combination of packets summing to exactly W - this is combinatorially expensive without a systematic bottom-up approach, when unbounded-knapsack-style DP computes it directly. Optimised: This is structurally identical to unbounded knapsack, just MINIMIZING cost instead of MAXIMIZING value - the same single-array 'reuse within the same pass' update rule applies directly, just with a min() instead of a max() at each step.

Keep the same recursive structure as brute force, but cache the minimum cost computed for each distinct remaining weight in a memo array the first time it's solved, and return the cached answer immediately on any repeat request for that same remaining weight. Since there are only W+1 distinct remaining-weight sub-problems and each does O(n) work trying every packet weight once, this turns the exponential brute force into a polynomial-time algorithm while keeping the natural recursive formulation. Time: O(n * W) Space: O(W)

Recursively try, for the remaining weight to fill, every available packet weight (skipping weights marked as unavailable with -1), and recurse on the remaining weight after subtracting it, taking the minimum total cost over all choices, with the base case that a remaining weight of 0 costs 0. This tries every possible combination of packets so it will find the true minimum, but the same remaining-weight sub-problems get recomputed repeatedly from scratch, causing exponential blowup. Time: O(n^W) exponential (unbounded branching without memoization) Space: O(W) recursion depth

Build a table dp[0..W] iteratively from the bottom up: dp[0] = 0, and for every weight w from 1 to W, dp[w] is the minimum over every available packet weight i of dp[w-i] + cost[i], with dp[w] left as infinity (meaning impossible) if no combination reaches it; the final answer is dp[W], or -1 if it's still infinity. This computes the identical result as the memoized recursion but fills the table iteratively with no function-call or recursion-depth overhead, which is a safe, predictable choice given W can be as large as 1000. Time: O(n * W) Space: O(W)

1. dp[w] = minimum cost to make exactly weight w; dp[0]=0. 2. For each weight w, try every packet weight i: if available and dp[w-i] is reachable, dp[w] = min(dp[w], dp[w-i] + cost[i]). 3. This is exactly UNBOUNDED KNAPSACK with a MINIMIZATION objective instead of maximization - if dp[W] is never updated, print -1.

Time: O(n * W) - for each of the W weights, trying all n packet types. Space: O(W), for the dp array.

Test cases where W can't be formed from the available weights (expect -1), where every weight is unavailable, and the upper bounds n = W = 1000 for performance.

Be ready to explicitly connect this to unbounded knapsack - recognizing that 'minimize cost' and 'maximize value' problems often share the exact same DP SKELETON, just flipping the comparison operator, is a valuable pattern-matching insight.