Class Knapsack01

java.lang.Object
topics.dynamic.knapsack.Knapsack01
public class Knapsack01 extends Object

0/1 Knapsack

Evaluates a set of items, each with a specific weight and value, to determine the combination that maximizes the total value without exceeding the weight limit of a knapsack. The "0/1" property dictates that an item must be taken entirely or left entirely (no fractions).

Dynamic Programming Transition Matrix (2D)

This implementation constructs a 2D matrix of size (N+1) × (W+1). Row 0 represents having "0 items" available (base case = 0 value). For each subsequent cell dp[i][w], we decide whether to:

  1. Leave the item: Inherit the maximum value from the row directly above dp[i-1][w].
  2. Take the item: Add the item's value to the maximum value found in the row above, shifted left by the item's weight: ItemValue + dp[i-1][w - ItemWeight].

Important Note on Input Data

In this specific educational implementation, the benefits array represents the value per unit of weight (Value/Kg), not the absolute value. Therefore, the total value of an item is calculated as: itemValue = benefits[i] * weights[i].

Complexity Analysis

  • Time Complexity: O(N × W) - Where N is items and W is max capacity.
  • Space Complexity: O(N × W) - Maintains the full historical state matrix for pedagogical clarity.
Author:
vicegd

  • Constructor Details

    • Knapsack01

      public Knapsack01()

  • Method Details

    • knapsack01

      public float knapsack01(int maxWeight, float[] benefits, int[] weights)
      Solves the 0/1 Knapsack problem using a 2D DP Matrix.
      Parameters:
      maxWeight - The absolute weight limit of the knapsack.
      benefits - The value per Kg for each item.
      weights - The absolute weight of each item.
      Returns:
      The maximum possible total value.