# Dynamic Programming Algorithms

• Dynamic programming algorithms divides a problem into multiple overlapping subproblems and build a solution (either bottom-up or top-down) only calculating the solution to a given subproblem once.

• Often involves some kind of cache or table to store intermediate solutions.

• Examples: Fibonacci, text-justification, knapsack problem.

## Knapsack Problem

• List of $n$ items, each with size $s_i$ and value $v_i$. Knapsack of size $S$. Choose subset of items of maximum total value subject to total size ≤ $S$.

• Subproblem: what is the maximum value of items starting at index $i$ with remaining size $X$?

• Recurrence:

K(i, X) = max(K(i + 1, X), v[i] + K(i + 1, X - s[i]) if s[i] ≤ X)

Base case:

K(n, X) = 0
• Solution

const int SENTINEL = -1;
vector<vector<int>> memo = vector<vector<int>>(NUMBER_OF_ITEMS + 1, vector<int>(KNSACK_SIZE + 1, SENTINEL));

int knapsackHelper(const vector<int> &weights, const vector<int> &values,
size_t i, int remainingSize) {
if (memo[i][remainingSize] == SENTINEL) {
// base case
if (i == weights.size()) {
} else if (weights[i] > remainingSize) {
answer = knapsackHelper(weights, values, i + 1, remainingSize);
} else {
int chooseThisItem = values[i] + knapsackHelper(weights, values, i + 1, remainingSize - weights[i]);
int notChooseThisItem = knapsackHelper(weights, values, i + 1, remainingSize);
}
}
return memo[i][remainingSize];
}

int knapsack(const vector<int> &weights, const vector<int> &values, int size) {
// return knapsackHelper(weights, values, 0, size);
// return iterativeKnapsack(weights, values, size);
return betterIterativeKnapsack(weights, values, size);
}
int iterativeKnapsack(const vector<int> &weights, const vector<int> &values, int size) {
vector<vector<int>> table = vector<vector<int>>(weights.size() + 1, vector<int>(size + 1));
// base case
for (size_t remainingSize = 0; remainingSize <= size; remainingSize += 1) {
size_t i = weights.size();
table[i][remainingSize] = 0;
}
for (int i = weights.size() - 1; i >= 0; i -= 1) {
for (int remainingSize = 0; remainingSize <= size; remainingSize += 1) {
if (weights[i] <= remainingSize) {
answer = max(values[i] + table[i + 1][remainingSize - weights[i]],
table[i + 1][remainingSize]);
} else {
}
}
}
return table[size];
}
int betterIterativeKnapsack(const vector<int> &weights, const vector<int> &values, int size) {
vector<int> currentRow = vector<int>(size + 1);
vector<int> previousRow = vector<int>(size + 1);
// base case
for (size_t remainingSize = 0; remainingSize < size; remainingSize += 1) {
previousRow[remainingSize] = 0;
}
for (int i = weights.size() - 1; i >= 0; i -= 1) {
for (int remainingSize = 0; remainingSize <= size; remainingSize += 1) {
if (weights[i] <= remainingSize) {
answer = max(values[i] + previousRow[remainingSize - weights[i]],
previousRow[remainingSize]);
} else {
}