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.

R DSA Implementation

basic.R

row_string <- function(row) paste0("[", paste(row, collapse = ", "), "]")
table_string <- function(table_rows) paste0("[", paste(apply(table_rows, 1, row_string), collapse = ", "), "]")
weights <- c(2, 3, 4, 5)
values <- c(3, 4, 5, 6)
capacity <- 5
dp <- matrix(0, nrow = length(weights) + 1, ncol = capacity + 1)
for (item in 1:length(weights)) {
  weight <- weights[item]
  value <- values[item]
  for (cap in 0:capacity) {
    if (weight > cap) {
      dp[item + 1, cap + 1] <- dp[item, cap + 1]
    } else {
      skip <- dp[item, cap + 1]
      take <- value + dp[item, cap - weight + 1]
      dp[item + 1, cap + 1] <- max(skip, take)
    }
  }
}
cat(dp[length(weights) + 1, capacity + 1], "\n", sep = "")
cat(table_string(dp), "\n", sep = "")

Implementation notes

The pinned inputs are weights <- c(2, 3, 4, 5), values <- c(3, 4, 5, 6), and capacity <- 5.
dp <- matrix(0, nrow = length(weights) + 1, ncol = capacity + 1) creates 5 rows and 6 columns: one row for zero items plus four item rows, and capacities 0 through 5.
R matrix indexes are 1-based, so the logical current row for item writes to dp[item + 1, cap + 1]. The previous row is read from dp[item, ...].
for (item in 1:length(weights)) selects weight <- weights[item] and value <- values[item].
for (cap in 0:capacity) scans capacities 0 through 5.
If weight > cap, the row inherits with dp[item + 1, cap + 1] <- dp[item, cap + 1].
Otherwise skip <- dp[item, cap + 1] and take <- value + dp[item, cap - weight + 1], then dp[item + 1, cap + 1] <- max(skip, take).

Replay rows

row0: [0, 0, 0, 0, 0, 0]
item1 w=2 v=3: [0, 0, 3, 3, 3, 3]
item2 w=3 v=4: [0, 0, 3, 4, 4, 7]
item3 w=4 v=5: [0, 0, 3, 4, 5, 7]
item4 w=5 v=6: [0, 0, 3, 4, 5, 7]

The final answer is dp[length(weights) + 1, capacity + 1], which is 7.
table_string(dp) uses apply(table_rows, 1, row_string) so the rows print deterministically, then the two cat(...) calls print the answer and table exactly as shown below.

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