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.

Perl DSA Implementation

basic.pl

use strict;
use warnings;

sub row_string { return "[" . join(", ", @_) . "]"; }
sub table_string { return "[" . join(", ", map { row_string(@$_) } @_) . "]"; }

my @weights = (2, 3, 4, 5);
my @values = (3, 4, 5, 6);
my $capacity = 5;
my @dp = map { [(0) x ($capacity + 1)] } 0..scalar(@weights);
for my $item (1..scalar(@weights)) {
  my $weight = $weights[$item - 1];
  my $value = $values[$item - 1];
  for my $cap (0..$capacity) {
    if ($weight > $cap) {
      $dp[$item][$cap] = $dp[$item - 1][$cap];
    } else {
      my $skip = $dp[$item - 1][$cap];
      my $take = $value + $dp[$item - 1][$cap - $weight];
      $dp[$item][$cap] = $skip > $take ? $skip : $take;
    }
  }
}
print "$dp[scalar(@weights)][$capacity]\n";
print table_string(@dp) . "\n";

Implementation notes

The checked item data is stored in two Perl arrays: @weights = (2, 3, 4, 5) and @values = (3, 4, 5, 6).
my $capacity = 5 means every row has columns for capacities 0 through 5.
my @dp = map { [(0) x ($capacity + 1)] } 0..scalar(@weights) builds five row array references: row 0 for no items, then one row after each of the four items.
Each row starts as [0, 0, 0, 0, 0, 0]. The [...] creates a separate row reference for each map pass.
Perl array indexes are zero-based here, so capacity cap is stored directly at $dp[$item][$cap].
The outer loop is for my $item (1..scalar(@weights)).
The current item reads from the parallel arrays with $item - 1: $weights[$item - 1] and $values[$item - 1].
The inner loop scans for my $cap (0..$capacity).
If the item is too heavy, $dp[$item][$cap] = $dp[$item - 1][$cap] copies the value from the previous row.
Otherwise, skip reads $dp[$item - 1][$cap] and take reads $value + $dp[$item - 1][$cap - $weight].
The update uses Perl's ternary expression: $dp[$item][$cap] = $skip > $take ? $skip : $take.

Table replay

row 0, no items:       [0, 0, 0, 0, 0, 0]
item 1, w=2, v=3:     [0, 0, 3, 3, 3, 3]
item 2, w=3, v=4:     [0, 0, 3, 4, 4, 7]
item 3, w=4, v=5:     [0, 0, 3, 4, 5, 7]
item 4, w=5, v=6:     [0, 0, 3, 4, 5, 7]

The final answer is $dp[scalar(@weights)][$capacity], which is 7.
table_string(@dp) maps each row through row_string(@$_) and prints the full table as [[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]].

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