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. @end @complexity

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

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

Dart DSA Implementation

basic.dart

String rowString(List<int> row) => "[${row.join(", ")}]";
String tableString(List<List<int>> table) => "[${table.map(rowString).join(", ")}]";

void main() {
  final weights = [2, 3, 4, 5];
  final values = [3, 4, 5, 6];
  const capacity = 5;
  final dp = List.generate(weights.length + 1, (_) => List<int>.filled(capacity + 1, 0));
  for (var item = 1; item <= weights.length; item++) {
    final weight = weights[item - 1];
    final value = values[item - 1];
    for (var cap = 0; cap <= capacity; cap++) {
      if (weight > cap) {
        dp[item][cap] = dp[item - 1][cap];
      } else {
        final skip = dp[item - 1][cap];
        final take = value + dp[item - 1][cap - weight];
        dp[item][cap] = skip > take ? skip : take;
      }
    }
  }
  print(dp[weights.length][capacity]);
  print(tableString(dp));
}

@end @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]] @end