Knapsack Problem Variants

Problem Explain and solve every standard form of the knapsack problem — 0/1, fractional, bounded, and unbounded. Given item weights, item values, and a capacity limit, maximise the total value carried without exceeding capacity, under each variant's rule on how many copies of an item may be taken.

Input / Output

• Input: arrays weights[] and values[] over n items, a capacity W, and (for the bounded variant) a per-item count limit c_i.
• Output: the maximum achievable value under each variant; optionally the chosen item set.

Constraints

• Weights, values and capacity are positive integers; 1 <= n <= 1000 and W up to ~10^4–10^5 for the DP variants.
• The DP is pseudo-polynomial: O(n·W) scales with the numeric value of W, not its bit length, so a very large W forces a different formulation.
• Only the fractional variant permits splitting an item.

Example

• weights = [10, 20, 30], values = [60, 100, 120], W = 50:
  • 0/1 → 220 (items 2 and 3).
  • Fractional → 240 (items 1 and 2 whole, then two-thirds of item 3).
  • Unbounded → 300 (five copies of item 1, the best ratio at 6.0 per unit weight).
• The gap between 220 and 240 is the point of the example: greedy by value/weight ratio is optimal for fractional and wrong for 0/1.