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

> Master knapsack problems with dynamic programming. Discover how to define states and apply transitions to maximize value efficiently. Learn the complete guide now.

- Repository: [hzwer/shareoi](https://github.com/hzwer/shareoi)
- Tags: tutorial
- Published: 2026-03-03

---

**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:

```python
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:

```python
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)

```python
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

```cpp
#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.