A knapsack problem involves selecting items with given weights and values to maximize total value without exceeding a capacity limit. It appears in resource allocation, scheduling, logistics, and investment scenarios.

Problem Categories

Binary Knapsack — Each item can be taken at most once. Given n items with weight wt[i] and value val[i], and capacity cap, choose subset maximizing sum of values within cap.

Unbounded Knapsack — Infinite copies of each item allowed. Maximize value with unlimited usage per item type under same capacity constraint.

Bounded Knapsack — Each item i has a limited copy count cnt[i]. Maximize value without exceeding both capacity and available counts.

---

Binary Knapsack: DP Formulation

Let f[i][c] = max value using first i items with capacity c. Transition:

• If wt[i-1] > c: f[i][c] = f[i-1][c]
• Else: f[i][c] = max(f[i-1][c], f[i-1][c - wt[i-1]] + val[i-1])

Implementation (Binary Knapsack)

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

using namespace std;

int solveBinaryKnapsack(vector<int>& wts, vector<int>& vals, int cap) {
    int n = wts.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    for (int idx = 1; idx <= n; ++idx) {
        for (int curCap = 1; curCap <= cap; ++curCap) {
            if (wts[idx - 1] <= curCap) {
                dp[idx][curCap] = max(dp[idx - 1][curCap],
                                      dp[idx - 1][curCap - wts[idx - 1]] + vals[idx - 1]);
            } else {
                dp[idx][curCap] = dp[idx - 1][curCap];
            }
        }
    }
    return dp[n][cap];
}

int main() {
    vector<int> itemWts = {2, 3, 1, 4};
    vector<int> itemVals = {3, 4, 2, 5};
    int knapsackCap = 5;
    cout << "Max attainable value: " << solveBinaryKnapsack(itemWts, itemVals, knapsackCap) << endl;
    return 0;
}

---

Unbounded Knapsack: DP Formulation

State idantical to binary version, but transition differs because an item may be reused:

• If wt[i-1] > c: f[i][c] = f[i-1][c]
• Else: f[i][c] = max(f[i-1][c], f[i][c - wt[i-1]] + val[i-1])

Implementation (Unbounded Knapsack)

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

using namespace std;

int solveUnboundedKnapsack(vector<int>& wts, vector<int>& vals, int cap) {
    int n = wts.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    for (int idx = 1; idx <= n; ++idx) {
        for (int curCap = 1; curCap <= cap; ++curCap) {
            if (wts[idx - 1] <= curCap) {
                dp[idx][curCap] = max(dp[idx - 1][curCap],
                                      dp[idx][curCap - wts[idx - 1]] + vals[idx - 1]);
            } else {
                dp[idx][curCap] = dp[idx - 1][curCap];
            }
        }
    }
    return dp[n][cap];
}

int main() {
    vector<int> itemWts = {2, 3, 1, 4};
    vector<int> itemVals = {3, 4, 2, 5};
    int knapsackCap = 5;
    cout << "Max attainable value: " << solveUnboundedKnapsack(itemWts, itemVals, knapsackCap) << endl;
    return 0;
}

---

Bounded Knapsack: Approaches

Naive Method

State: f[i][c] = max value from first i items with capacity c. For each (i,c), try all feasible counts k of item i:

f[i][c] = max_{0 ≤ k ≤ cnt[i], k*wt[i] ≤ c} ( f[i-1][c - k*wt[i]] + k*val[i] )

Time complexity: O(n * cap * Σcnt[i]).

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

using namespace std;

int solveBoundedNaive(vector<int>& wts, vector<int>& vals, vector<int>& counts, int cap) {
    int n = wts.size();
    vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));

    for (int idx = 1; idx <= n; ++idx) {
        for (int curCap = 1; curCap <= cap; ++curCap) {
            for (int k = 0; k <= counts[idx - 1] && k * wts[idx - 1] <= curCap; ++k) {
                dp[idx][curCap] = max(dp[idx][curCap],
                    dp[idx - 1][curCap - k * wts[idx - 1]] + k * vals[idx - 1]);
            }
        }
    }
    return dp[n][cap];
}

int main() {
    vector<int> wts = {2, 3, 1};
    vector<int> vals = {3, 4, 2};
    vector<int> limits = {2, 1, 3};
    int cap = 6;
    cout << "Max value: " << solveBoundedNaive(wts, vals, limits, cap) << endl;
    return 0;
}

Binary Splitting Optimization

Decompose each count into powers of two (1, 2, 4, …) plus remainder, converting bounded case into binary knapsack:

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

using namespace std;

int solveBoundedOptimized(vector<int>& wts, vector<int>& vals, vector<int>& counts, int cap) {
    vector<int> splitWts, splitVals;
    for (int i = 0; i < wts.size(); ++i) {
        int remaining = counts[i];
        for (int k = 1; k <= remaining; k <<= 1) {
            splitWts.push_back(k * wts[i]);
            splitVals.push_back(k * vals[i]);
            remaining -= k;
        }
        if (remaining > 0) {
            splitWts.push_back(remaining * wts[i]);
            splitVals.push_back(remaining * vals[i]);
        }
    }

    int m = splitWts.size();
    vector<int> dp(cap + 1, 0);
    for (int i = 0; i < m; ++i) {
        for (int c = cap; c >= splitWts[i]; --c) {
            dp[c] = max(dp[c], dp[c - splitWts[i]] + splitVals[i]);
        }
    }
    return dp[cap];
}

int main() {
    vector<int> wts = {2, 3, 1};
    vector<int> vals = {3, 4, 2};
    vector<int> limits = {2, 1, 3};
    int cap = 6;
    cout << "Max value: " << solveBoundedOptimized(wts, vals, limits, cap) << endl;
    return 0;
}

---

Space Optimization for Binary Case

Because dp[i][c] depends only on previous row, collapse to 1D array and iterate capacities backward to avoid reuse:

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

using namespace std;

int solveBinaryOptimizedSpace(vector<int>& wts, vector<int>& vals, int cap) {
    vector<int> dp(cap + 1, 0);
    for (int i = 0; i < wts.size(); ++i) {
        for (int c = cap; c >= wts[i]; --c) {
            dp[c] = max(dp[c], dp[c - wts[i]] + vals[i]);
        }
    }
    return dp[cap];
}

int main() {
    vector<int> wts = {2, 3, 1, 4};
    vector<int> vals = {3, 4, 2, 5};
    int cap = 5;
    cout << "Max value: " << solveBinaryOptimizedSpace(wts, vals, cap) << endl;
    return 0;
}

---

Practical Use Cases

Travel Packing — Treat luggage as knapsack, items as clothing or gear with space/weight and utility scores; select combination maximizing usefulness within volume limit.

Resource Allocation in Projects — Treat team effort or budget as capacity, tasks as items with required effort and expected gain; maximize gain within constraints.

Example: project task selection modeled as binary knapsack:

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

using namespace std;

int planTasks(vector<int>& efforts, vector<int>& gains, int budget) {
    int n = efforts.size();
    vector<int> dp(budget + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int b = budget; b >= efforts[i]; --b) {
            dp[b] = max(dp[b], dp[b - efforts[i]] + gains[i]);
        }
    }
    return dp[budget];
}

int main() {
    vector<int> effortReq = {2, 3, 1, 4};
    vector<int> profitEst = {3, 4, 2, 5};
    int totalBudget = 5;
    cout << "Best achievable profit: " << planTasks(effortReq, profitEst, totalBudget) << endl;
    return 0;
}