0/1 Knapsack (Small)

Fill a small 0/1 knapsack table where each row decides whether one more item is available.

Algorithm

Steps

Create a table with one extra row for using zero items.
Process the four items in fixed order.
For each capacity, inherit when the item is too heavy.
Otherwise compare skip and take from the previous row.
Print the best value and the full deterministic table.

Complexity

Time: O(item_count * capacity)
Space: O(item_count * capacity)

state transition `dp[i][w]` compares skipping item `i` with taking it and reading the remaining capacity from the previous row.

Java DSA Implementation

Basic.java

public class Basic {
  static String rowString(int[] row) {
    StringBuilder out = new StringBuilder("[");
    for (int i = 0; i < row.length; i++) {
      if (i > 0) out.append(", ");
      out.append(row[i]);
    }
    return out.append("]").toString();
  }
  static String tableString(int[][] table) {
    StringBuilder out = new StringBuilder("[");
    for (int i = 0; i < table.length; i++) {
      if (i > 0) out.append(", ");
      out.append(rowString(table[i]));
    }
    return out.append("]").toString();
  }
  public static void main(String[] args) {
    int[] weights = {2, 3, 4, 5};
    int[] values = {3, 4, 5, 6};
    int capacity = 5;
    int[][] dp = new int[weights.length + 1][capacity + 1];
    for (int item = 1; item <= weights.length; item++) {
      int weight = weights[item - 1];
      int value = values[item - 1];
      for (int cap = 0; cap <= capacity; cap++) {
        if (weight > cap) dp[item][cap] = dp[item - 1][cap];
        else {
          int skip = dp[item - 1][cap];
          int take = value + dp[item - 1][cap - weight];
          dp[item][cap] = Math.max(skip, take);
        }
      }
    }
    System.out.println(dp[weights.length][capacity]);
    System.out.println(tableString(dp));
  }
}

Output

7
[[0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], [0, 0, 3, 4, 5, 7]]

Implementation notes

Java stores weights and values in primitive int[] arrays and the DP table in an int[][] allocated as new int[weights.length + 1][capacity + 1]. The table starts with Java's default zero initialization, so row 0 already represents using no items.
The outer loop is item-first: item runs from 1 through weights.length, then binds weight = weights[item - 1] and value = values[item - 1]. The inner cap loop fills capacities 0 through capacity.
If weight > cap, the current cell copies dp[item - 1][cap]. Otherwise skip and take = value + dp[item - 1][cap - weight] are primitive int candidates, and Math.max(skip, take) writes the chosen value into the current row.
The small checked-in values keep integer sums far from overflow. The replay exposes whole row states, ending with row 4 as [0, 0, 3, 4, 5, 7] and answer 7.
In Java, int[][] is an array of row arrays, so allocation is the outer reference array plus one primitive row array per item count. The custom rowString and tableString helpers allocate StringBuilder objects, builder backing storage, and returned String objects for deterministic output, all managed by JVM GC.