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.c

#include <stdio.h>

void print_table(int table[5][6]) {
  printf("[");
  for (int i = 0; i < 5; i++) {
    if (i > 0) printf(", ");
    printf("[");
    for (int w = 0; w < 6; w++) {
      if (w > 0) printf(", ");
      printf("%d", table[i][w]);
    }
    printf("]");
  }
  printf("]\n");
}

int main(void) {
  int weights[] = {2, 3, 4, 5};
  int values[] = {3, 4, 5, 6};
  int capacity = 5;
  int dp[5][6] = {0};
  for (int item = 1; item <= 4; 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] = skip > take ? skip : take;
      }
    }
  }
  printf("%d\n", dp[4][5]);
  print_table(dp);
  return 0;
}

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

C stores weights and values as parallel stack arrays {2, 3, 4, 5} and {3, 4, 5, 6}.
The DP table is fixed stack storage int dp[5][6] = {0}: five rows for zero through four items and six columns for capacities 0..5. There is no sentinel; C zero-initialization supplies the base row and capacity-zero column.
The outer loop scans item = 1..4, then maps to C array slots weights[item - 1] and values[item - 1]. The inner loop scans cap = 0..capacity.
When weight > cap, the cell copies dp[item - 1][cap]; otherwise it computes skip = dp[item - 1][cap] and take = value + dp[item - 1][cap - weight], then writes the larger value with the ternary expression.
The trace records row transitions [0, 0, 0, 0, 0, 0], [0, 0, 3, 3, 3, 3], [0, 0, 3, 4, 4, 7], [0, 0, 3, 4, 5, 7], and [0, 0, 3, 4, 5, 7].
printf("%d\n", dp[4][5]) prints the best value, then print_table(int table[5][6]) formats all rows. The table parameter decays to a pointer to six-int rows while preserving the column width in the signature.