Core Implementation Strategy

Resolving knapsack variations follows a structured pattern involving state definition, initialization, and recurrence relation formulation. The primary distinction lies in whether an item can be selected multiple times or only once.

Phase 1: 0-1 Knapsack Variant

In this scenario, each item is available exact once per solution instance. The goal is to maximize profit within a given weight limit.

Implementation via 2D Table

This method tracks the maximum profit obtainable considering the first i items against a capacity limit j. A two-dimensional array dp[i][c] represents the optimal value using subset of items up to index i with capacity c.

#include <iostream>
#include <vector>
#include <algorithm>

class KnapSolver {
public:
    int computeMaxProfit(const std::vector<int>& weights,
                         const std::vector<int>& values,
                         int itemCount, int maxCap) {
        
        std::vector<std::vector<int>> table(itemCount, std::vector<int>(maxCap + 1, 0));
        
        // Initialize first row based on the first item
        for (int j = weights[0]; j <= maxCap; ++j) {
            table[0][j] = values[0];
        }

        // Fill table
        for (int i = 1; i < itemCount; ++i) {
            for (int j = 1; j <= maxCap; ++j) {
                if (weights[i] > j) {
                    table[i][j] = table[i - 1][j];
                } else {
                    table[i][j] = std::max(table[i - 1][j], 
                                           table[i - 1][j - weights[i]] + values[i]);
                }
            }
        }
        return table[itemCount - 1][maxCap];
    }
};

int main() {
    int n, m;
    if (std::cin >> n >> m) {
        std::vector<int> weights(n);
        std::vector<int> values(n);
        
        for (int i = 0; i < n; ++i) std::cin >> weights[i];
        for (int i = 0; i < n; ++i) std::cin >> values[i];

        KnapSolver solver;
        std::cout << solver.computeMaxProfit(weights, values, n, m) << std::endl;
    }
    return 0;
}

Optimization to 1D Rolling Array

By observing that the current row depends solely on the previous row, memory usage reduces to $O(V)$. To prevent overwriting values required for the current calculation, traverse the capacity dimension in descending order.

#include <iostream>
#include <vector>
#include <algorithm>

class OptimizedKnapSolver {
public:
    int calculateMaxValue(const std::vector<int>& weights,
                          const std::vector<int>& values,
                          int itemCount, int maxCap) {
        
        std::vector<int> cache(maxCap + 1, 0);

        for (int i = 0; i < itemCount; ++i) {
            for (int j = maxCap; j >= weights[i]; --j) {
                cache[j] = std::max(cache[j], cache[j - weights[i]] + values[i]);
            }
        }
        return cache[maxCap];
    }
};

int main() {
    int n, m;
    if (std::cin >> n >> m) {
        std::vector<int> weights(n);
        std::vector<int> values(n);
        
        for (int i = 0; i < n; ++i) std::cin >> weights[i];
        for (int i = 0; i < n; ++i) std::cin >> values[i];

        OptimizedKnapSolver solver;
        std::cout << solver.calculateMaxValue(weights, values, n, m) << std::endl;
    }
    return 0;
}

Phase 2: Complete Knapsack Variant

This scenario permits infinite instances of each item type, subject to total capacity constraints.

Implementation via 2D Table

Similar to the 0-1 case, but the trensition equation utilizes the current item row dp[i][j-weight] instead of the previous row dp[i-1][j-weight], allowing reuse of the current item in the same capacity step.

#include <iostream>
#include <vector>
#include <algorithm>

class CompleteKnapSolver {
public:
    int computeFullUnboundValue(const std::vector<int>& weights,
                                const std::vector<int>& values,
                                int itemCount, int maxCap) {
        
        std::vector<std::vector<int>> dp(itemCount, std::vector<int>(maxCap + 1, 0));
        
        // Initialization handles multiple copies for the first item
        for (int j = weights[0]; j <= maxCap; ++j) {
            dp[0][j] = dp[0][j - weights[0]] + values[0];
        }

        for (int i = 1; i < itemCount; ++i) {
            for (int j = 1; j <= maxCap; ++j) {
                if (weights[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = std::max(dp[i - 1][j], 
                                        dp[i][j - weights[i]] + values[i]);
                }
            }
        }
        return dp[itemCount - 1][maxCap];
    }
};

int main() {
    int n, m;
    if (std::cin >> n >> m) {
        std::vector<int> weights(n);
        std::vector<int> values(n);
        
        for (int i = 0; i < n; ++i) {
            std::cin >> weights[i] >> values[i];
        }

        CompleteKnapSolver solver;
        std::cout << solver.computeFullUnboundValue(weights, values, n, m) << std::endl;
    }
    return 0;
}

Optimization to 1D Array

In the complete knapsack problem, since multiple copies of a item can fill the bag, we iterate through the capacity in ascending order. This allows dp[j-weight] to already reflect the inclusion of the current item before calculating for capacity j.

#include <iostream>
#include <vector>
#include <algorithm>

class OptimizedCompleteSolver {
public:
    int getOptimalUnboundValue(const std::vector<int>& weights,
                               const std::vector<int>& values,
                               int itemCount, int maxCap) {
        
        std::vector<int> dp(maxCap + 1, 0);

        for (int i = 0; i < itemCount; ++i) {
            for (int j = weights[i]; j <= maxCap; ++j) {
                dp[j] = std::max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        return dp[maxCap];
    }
};

int main() {
    int n, m;
    if (std::cin >> n >> m) {
        std::vector<int> weights(n);
        std::vector<int> values(n);
        
        for (int i = 0; i < n; ++i) {
            std::cin >> weights[i] >> values[i];
        }

        OptimizedCompleteSolver solver;
        std::cout << solver.getOptimalUnboundValue(weights, values, n, m) << std::endl;
    }
    return 0;
}