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

#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

string row_string(const vector<int>& row) {
  ostringstream out;
  out << "[";
  for (size_t i = 0; i < row.size(); i++) {
    if (i) out << ", ";
    out << row[i];
  }
  out << "]";
  return out.str();
}
string table_string(const vector<vector<int>>& table) {
  ostringstream out;
  out << "[";
  for (size_t i = 0; i < table.size(); i++) {
    if (i) out << ", ";
    out << row_string(table[i]);
  }
  out << "]";
  return out.str();
}
int main() {
  vector<int> weights = {2, 3, 4, 5};
  vector<int> values = {3, 4, 5, 6};
  int capacity = 5;
  vector<vector<int>> dp(weights.size() + 1, vector<int>(capacity + 1, 0));
  for (int item = 1; item <= (int)weights.size(); 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 dp[item][cap] = max(dp[item - 1][cap], value + dp[item - 1][cap - weight]);
    }
  }
  cout << dp[weights.size()][capacity] << "\n" << table_string(dp) << "\n";
}

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

In C++, weights and values are parallel std::vector<int> objects: {2, 3, 4, 5} and {3, 4, 5, 6}.
The DP table is std::vector<std::vector<int>> dp(weights.size() + 1, std::vector<int>(capacity + 1, 0)), giving five independent rows and six columns for capacity 0..5.
The outer loop casts weights.size() to int and scans item = 1..4; weight and value are copied from item - 1, then the inner loop scans cap = 0..5.
Each cell writes into dp[item][cap]: either a copy from the previous row when weight > cap, or max(dp[item - 1][cap], value + dp[item - 1][cap - weight]).
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].
table_string(const std::vector<std::vector<int>>& table) reads rows by const reference and calls row_string(table[i]); both formatting helpers use std::ostringstream before std::cout prints 7 and then the full table. Visible allocation is the weights, values, table rows, and formatting buffers; visible mutation is confined to DP cells.