How to Solve Knapsack Problems Using Dynamic Programming: A Complete Guide

Dynamic programming solves knapsack problems by defining a state dp[w] that stores the maximum value achievable with capacity w, then iteratively applying state transitions that either include or exclude each item to exploit optimal substructure.

The knapsack problem is a cornerstone of algorithmic optimization, frequently appearing in competitive programming and resource allocation scenarios. This guide draws from the hzwer/shareoi repository, specifically the lecture notes in 背包与树形_黄哲威.pdf, to explain how to solve knapsack problems using dynamic programming with concrete state definitions and optimized implementations.

Understanding the Knapsack Problem Structure

The knapsack problem exhibits two properties that make it ideal for dynamic programming: optimal substructure and overlapping subproblems. According to the analysis in 背包与树形_黄哲威.pdf, any optimal solution to a knapsack instance contains optimal solutions to its sub-instances with smaller capacities.

When solving knapsack problems using dynamic programming, you avoid the exponential complexity of brute-force enumeration by caching results of subproblems in a table. This approach reduces the time complexity from O(2^N) to O(N·W), where N is the number of items and W is the knapsack capacity.

Dynamic Programming State Definition

The foundation of any knapsack DP solution is the state definition. As detailed in the repository's 动态规划入门_黄哲威.pdf, you define dp[i][w] as the maximum value achievable using the first i items with a total weight not exceeding w.

However, the lecture notes emphasize a crucial space optimization: because each state dp[i][w] only depends on dp[i-1][*], you can compress the table to a one-dimensional array dp[w]. This reduces space complexity from O(N·W) to O(W).

State Transitions for Different Knapsack Variants

The transition logic varies depending on whether items can be used once or multiple times. The 背包与树形_黄哲威.pdf file provides distinct recurrence relations for each variant.

0-1 Knapsack (Descending Loop)

In the 0-1 knapsack problem, each item can be selected at most once. The state transition is:

dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

Crucially, you must iterate w from W down to weight[i] (descending order). This prevents using the same item multiple times, as dp[w - weight[i]] still contains the values from the previous iteration (i-1), not the current one.

Complete Knapsack (Ascending Loop)

In the complete (unbounded) knapsack problem, items can be selected unlimited times. The transition formula appears identical:

dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

However, you iterate w from weight[i] up to W (ascending order). This allows dp[w - weight[i]] to potentially include the current item already, effectively permitting unlimited reuse.

Space Optimization Techniques

The repository's lecture notes emphasize reducing memory usage while maintaining correctness. The standard optimization involves:

1. 1D Array Reduction: Replace dp[i][w] with dp[w], updating in-place.
2. Loop Direction Control: Use descending loops for 0-1 knapsack to prevent item reuse, ascending for complete knapsack to allow it.
3. Initialization: Set all dp entries to 0, representing zero value for zero items.

These techniques achieve O(W) space complexity, essential for handling large capacity constraints up to 10^5 or higher in competitive programming environments.

Implementation Examples

The following implementations reflect the textbook dynamic programming approaches described in 背包与树形_黄哲威.pdf.

Python: 0-1 Knapsack (Space-Optimized)

def knapsack_01(weights, values, capacity):
    """Return maximum value obtainable with given capacity."""
    dp = [0] * (capacity + 1)                # dp[w] = best value for weight w

    for w_i, v_i in zip(weights, values):
        for w in range(capacity, w_i - 1, -1):  # descend to avoid reuse

            dp[w] = max(dp[w], dp[w - w_i] + v_i)
    return dp[capacity]

# Example

w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
C = 5
print(knapsack_01(w, v, C))   # → 7  (items 0 and 1)

C++: Complete (Unbounded) Knapsack

#include <bits/stdc++.h>
using namespace std;

int unboundedKnapsack(const vector<int>& wt,
                      const vector<int>& val,
                      int W) {
    vector<int> dp(W + 1, 0);               // dp[w] = best value for weight w
    for (size_t i = 0; i < wt.size(); ++i) {
        for (int w = wt[i]; w <= W; ++w) { // ascend → unlimited reuse
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> w = {2, 3, 4};
    vector<int> v = {3, 4, 5};
    int C = 10;
    cout << unboundedKnapsack(w, v, C) << endl; // → 15 (use item 0 five times)
    return 0;
}

Both snippets directly implement the recurrence relations and space-compression strategies detailed in the repository's lecture notes.

Advanced Resources in hzwer/shareoi

The hzwer/shareoi repository contains several supplementary materials that extend beyond basic knapsack implementations:

• 动态规划入门_黄哲威.pdf – Covers foundational DP concepts including state definition and initialization patterns essential for knapsack variants.
• 动态规划_钱雨杰.pptx – Contains slide decks with visual explanations of DP transitions and complexity analysis.
• 基础算法/贪心问题选讲_王天懿.ppt – Helps distinguish between greedy approaches and DP solutions for knapsack-like problems.
• 图论/树形动态规划_朱全民.ppt – Extends knapsack concepts to tree structures, useful for dependent knapsack problems where items have hierarchical relationships.

These resources collectively provide the theoretical background and practical optimization techniques needed to master knapsack problems in competitive programming contexts.

Summary

• Dynamic programming solves knapsack problems by exploiting optimal substructure and overlapping subproblems, reducing complexity from exponential to pseudo-polynomial O(N·W).
• State definition uses dp[w] to represent the maximum value achievable with capacity w, compressing the standard 2D dp[i][w] to O(W) space.
• 0-1 knapsack requires descending iteration over capacity to prevent item reuse, while complete knapsack uses ascending iteration to allow unlimited selection.
• The hzwer/shareoi repository provides authoritative reference material in 背包与树形_黄哲威.pdf, including recurrence derivations, complexity analysis, and extensions to tree-based knapsack variants.

Frequently Asked Questions

What is the time complexity of the dynamic programming solution for knapsack problems?

The standard dynamic programming solution for knapsack problems runs in O(N·W) time, where N is the number of items and W is the knapsack capacity. This pseudo-polynomial complexity arises because the algorithm fills a DP table with N·W states, performing constant-time transition operations for each state. For large capacities (e.g., W > 10^9), alternative approaches like meet-in-the-middle or value-oriented DP become necessary.

How does the 0-1 knapsack differ from the complete knapsack in DP implementation?

While both variants use the state transition dp[w] = max(dp[w], dp[w - weight[i]] + value[i]), they differ critically in iteration direction. The 0-1 knapsack iterates capacity descending from W to weight[i], ensuring each item is used at most once by preventing the current item from being included in the subproblem solution. The complete knapsack iterates ascending from weight[i] to W, allowing the current item to be reused indefinitely because dp[w - weight[i]] may already include the current item.

Can the knapsack DP approach be extended to tree structures?

Yes, knapsack dynamic programming extends naturally to tree-shaped DP (树形DP), where items have hierarchical dependencies rather than linear independence. As documented in 图论/树形动态规划_朱全民.ppt and 背包与树形_黄哲威.pdf, tree knapsack problems require merging child node DP tables into parent nodes using a grouped knapsack transition. Each node represents an item with a weight (cost), and you must decide which subtree items to include while respecting the knapsack capacity constraint.

When should I use value-oriented DP instead of weight-oriented DP?

Use value-oriented DP when the knapsack capacity W is extremely large (e.g., 10^9) but the total value sum V is relatively small (e.g., 10^5). Instead of defining dp[w] as the maximum value for weight w, define dp[v] as the minimum weight required to achieve value v. The answer becomes the largest v where dp[v] ≤ W. This approach, mentioned in 背包与树形_黄哲威.pdf, changes the complexity to O(N·V) time and space, making it feasible when value sums are bounded but weights are not.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}