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.

C# DSA Implementation

basic.cs

using System;
using System.Linq;

string RowString(int[] row) => "[" + string.Join(", ", row) + "]";
string TableString(int[][] table) => "[" + string.Join(", ", table.Select(RowString)) + "]";

int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 5;
int[][] dp = Enumerable.Range(0, weights.Length + 1).Select(_ => new int[capacity + 1]).ToArray();
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);
    }
  }
}
Console.WriteLine(dp[weights.Length][capacity]);
Console.WriteLine(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

weights and values are int[] arrays, and the DP table is a jagged int[][], not int[,]. `Enumerable.Range(...).Select(_ => new int[capacity
- 1]).ToArray()` allocates one managed row array per item state plus the outer row-reference array, leaving those arrays GC-managed once no references remain.
The loops fill rows by item, then capacities from 0 through capacity. weight > cap avoids reading cap - weight when it would be negative, and CLR bounds checks still protect each dp[item][cap] access.
skip, take, and Math.Max(skip, take) operate on copied int values. The trace shows each completed row, matching the row-array updates that feed the printed jagged table.