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) {
        // compute answer
        int answer;
        // base case
        if (i == weights.size()) {
            answer = 0;
        } 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);
            answer = max(chooseThisItem, notChooseThisItem);
        }
        memo[i][remainingSize] = answer;
    }
    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) {
            int answer;
            if (weights[i] <= remainingSize) {
                answer = max(values[i] + table[i + 1][remainingSize - weights[i]],
                             table[i + 1][remainingSize]);
            } else {
                answer = table[i + 1][remainingSize];
            }
            table[i][remainingSize] = answer;
        }
    }
    return table[0][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) {
            int answer;
            if (weights[i] <= remainingSize) {
                answer = max(values[i] + previousRow[remainingSize - weights[i]],
                             previousRow[remainingSize]);
            } else {
                answer = previousRow[remainingSize];
            }
            currentRow[remainingSize] = answer;
        }
        swap(currentRow, previousRow);
    }
    return previousRow[size];
}

Dynamic Programming

Dynamic Programming Algorithms

Knapsack Problem

results matching ""

No results matching ""