Solving the 0/1 Knapsack Problem: Brute Force, Greedy, Dynamic Programming, and Branch-and-Bound

Verified Sources

May 27, 2026

The 0/1 Knapsack Problem is a classical combinatorial optimization problem: given $n$ items, where item $i$ has weight $w_i$ and value $v_i$ , choose a subset that maximizes total value subject to a capacity limit $W$ .2 Unlike the fractional knapsack problem, each item in 0/1 knapsack is either taken completely or not taken at all.2

The standard mathematical formulation is:

\max \sum_{i=1}^{n} v_i x_i

subject to

\sum_{i=1}^{n} w_i x_i \le W,\qquad x_i \in \{0,1\}

where $x_i = 1$ means item $i$ is selected and $x_i = 0$ means it is not selected.2

This problem is important because it captures the structure of many real decision tasks: budgeted project selection, cargo loading, memory allocation, and resource planning.2 In this section, we compare four major approaches:

Brute force
Greedy method
Dynamic programming
Branch-and-bound

A key theme is that all four methods trade off optimality, speed, and scalability differently.2

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩ ↩² ↩³ ↩⁴ ↩⁵
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩² ↩³ ↩⁴ ↩⁵
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩ ↩²
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩

0/1 Knapsack - Two Methods - Dynamic Programming

Core Distinction

The 0/1 version forbids splitting items. This single restriction is why greedy-by-ratio works for fractional knapsack but can fail for 0/1 knapsack.2

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩

Problem intuition and evaluation criteria

When comparing algorithms for this problem, three criteria matter most:

Correctness: does the algorithm always return an optimal subset?2
Time complexity: how does runtime grow with the number of items $n$ and capacity $W$ ?2
Practical limitation: what kind of instances make the method weak or unusable?2

A useful classification is shown below.

Approach	Optimal?	Typical Idea	Time Complexity	Main Limitation
Brute force	Yes	Enumerate all subsets	$O(2^n)$	Explodes exponentially
Greedy	No, not in general	Pick items by a local rule	Often $O(n \log n)$ after sorting	Local choices can block global optimum
Dynamic programming	Yes	Table of best values for prefixes and capacities	$O(nW)$	Depends on numeric capacity; pseudo-polynomial
Branch-and-bound	Yes	Search tree + prune using upper bounds	Worst case $O(2^n)$	Performance is instance-dependent

This table reflects a classic algorithm-design pattern: exhaustive search gives certainty, heuristics give speed, and structured optimization methods try to balance both.3

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩ ↩² ↩³ ↩⁴
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩²
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩ ↩²
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩

Conceptual Roadmap for Solving 0/1 Knapsack

Model the decision

Stage 1

Represent each item by a binary decision variable $x_i \in \{0,1\}$ and enforce the capacity constraint.2"

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

Try direct enumeration

Stage 2

Brute force considers every subset and guarantees optimality, but runtime is exponential."

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩

Use local heuristics

Stage 3

Greedy strategies sort items by value, weight, or value-to-weight ratio, but can miss the best subset in the 0/1 case.2"

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩

Exploit subproblem structure

Stage 4

Dynamic programming uses overlapping subproblems to compute the optimal answer in $O(nW)$ time.2"

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩

Prune the search

Stage 5

Branch-and-bound explores a state-space tree and cuts off nodes whose best possible completion cannot beat the current best solution.2"

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩

(i) Brute-force method

The brute-force approach generates every possible subset of the $n$ items and evaluates whether it fits within capacity $W$ .2 Since each item has two states—take or skip—there are $2^n$ subsets in total.2

For each subset, the algorithm computes:

total weight $= \sum w_i x_i$
total value $= \sum v_i x_i$

and keeps the feasible subset with maximum value.

A simple recursive viewpoint is:

for item $i$ , either include it or exclude it;
recursively solve both branches;
choose the better feasible result.

This gives the recurrence intuition:

K(i, c) = \begin{cases} 0, & \text{if } i=0 \text{ or } c=0 \\ \max\big(K(i-1,c),\ v_i + K(i-1, c-w_i)\big), & \text{if } w_i \le c \\ K(i-1,c), & \text{if } w_i > c \end{cases}

Without memoization, this recursion repeatedly recomputes the same subproblems, causing exponential behavior.

Time complexity

The brute-force search examines all subsets, so the time complexity is $O(2^n)$ .2 Space usage is typically $O(n)$ for recursive depth, ignoring storage of all subsets.

Limitations

Brute force is conceptually simple and always optimal, but becomes impractical even for moderate $n$ because exponential growth is extremely fast.2 It is mainly useful:

as a teaching baseline,
for very small inputs,
or for verifying other implementations.

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸

Brute-Force Walkthrough

1
Step 1
For every item, decide between including it or excluding it. This creates a binary decision tree with $2^n$ leaves.2

Footnotes

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩
2
Step 2
Enumerate every possible combination of selected items using recursion, bit masks, or subset generation.

Footnotes

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
3
Step 3
For each subset, compute total weight and discard the subset if it exceeds capacity $W$ .2

Footnotes

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩
4
Step 4
For each feasible subset, compute total value and compare it with the best value seen so far.

Footnotes

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
5
Step 5
After all subsets have been examined, output the feasible subset with maximum total value.

Footnotes

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩

Why brute force scales poorly

Doubling the number of items roughly squares the number of subsets examined, because the search space grows like $2^n$ .2

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩

(ii) Greedy method

A greedy algorithm builds a solution incrementally by selecting the item that looks best according to a local rule.2 For knapsack, common greedy rules are:

choose highest value first,
choose smallest weight first,
choose highest value-to-weight ratio $\frac{v_i}{w_i}$ first.2

The ratio-based rule is the most sensible and is optimal for the fractional knapsack problem, because fractional inclusion allows a partially chosen last item.3 However, in the 0/1 problem, items are indivisible, so a locally attractive choice may prevent a better global combination.2

A common greedy algorithm is:

compute density $\frac{v_i}{w_i}$ for each item,
sort items in descending order of density,
scan the sorted list,
include an item if it fits; otherwise skip it.2

Time complexity

If sorting is used, the runtime is typically $O(n \log n)$ , followed by an $O(n)$ scan. So the total is usually $O(n \log n)$ .

Why greedy may fail

The issue is that 0/1 knapsack does not satisfy the greedy-choice property needed for guaranteed optimality.2 A counterexample makes this clear.

Suppose capacity $W = 50$ and items are:

Item	Weight	Value	Ratio $\frac{v}{w}$
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

A ratio-based greedy algorithm picks A first, then B, giving total weight $30$ and total value $160$ . Item C no longer fits with both A and B.
But the optimal 0/1 solution is B + C, with weight $50$ and value $220$ , which is much better.

So the greedy choice is locally appealing but globally inferior.

Limitations

Greedy is fast and simple, but it is a heuristic for the 0/1 problem.2 It may work well on some instances, yet there is no guarantee that it returns the optimal answer.2

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹ ↩¹² ↩¹³
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩²
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
SI335: 0/1 Knapsack - Greed is bad - Notes that multiple greedy choices fail to always produce an optimal 0/1 knapsack solution. ↩ ↩² ↩³

Compute density $v_i / w_i$ for each item.
Sort items from highest to lowest density.
Add the next item if it fits; otherwise skip it.
Stop when all items are considered.

Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩ ↩² ↩³

The failure of greediness can be visualized as a mismatch between local ranking and global feasibility.

In other words, the greedy method optimizes the next step, not the entire subset structure.2 This is why it is important to distinguish between:

heuristic performance,
and optimal algorithm performance.

Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩ ↩²
SI335: 0/1 Knapsack - Greed is bad - Notes that multiple greedy choices fail to always produce an optimal 0/1 knapsack solution. ↩ ↩²

(iii) Dynamic Programming

Dynamic programming is the standard exact approach for 0/1 knapsack because the problem has overlapping subproblems and optimal substructure.2

Define $DP[i][c]$ as the maximum value achievable using the first $i$ items with capacity $c$ .2 Then:

DP[i][c] = \begin{cases} DP[i-1][c], & \text{if } w_i > c \\ \max\big(DP[i-1][c],\ v_i + DP[i-1][c-w_i]\big), & \text{if } w_i \le c \end{cases}

with base cases

DP[0][c] = 0,\qquad DP[i][0] = 0.

Interpretation:

if item $i$ is too heavy, we must skip it;
otherwise, compare skipping it versus taking it.2

The final answer is $DP[n][W]$ .2

This method systematically computes all subproblems once and stores them in a table, eliminating repeated recursion.2

Time complexity

The table has $(n+1)(W+1)$ states, and each state is filled in constant time, so the runtime is $O(nW)$ .3

Space complexity

A full table uses $O(nW)$ space. A space-optimized 1D version uses only $O(W)$ space by iterating capacities backward.

Limitations

Dynamic programming is exact and often practical for small to medium capacities, but its complexity depends on the numeric value of $W$ , not only on the input length.2 Therefore it is pseudo-polynomial rather than polynomial in the formal complexity-theory sense.

If $W$ is very large, the table can become too large in time and memory.3

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰
0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩ ↩² ↩³ ↩⁴

Dynamic Programming Table Construction

1
Step 1
Build a table with rows for item prefixes $0$ to $n$ and columns for capacities $0$ to $W$ .2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩
2
Step 2
Set the first row and first column to $0$ , because zero items or zero capacity yield zero value.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩
3
Step 3
For each item $i$ , inspect every capacity $c$ from $0$ to $W$ and decide whether the item can fit.

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
4
Step 4
If $w_i \le c$ , write the larger of skipping the item or taking it with the best value available at capacity $c-w_i$ from the previous row.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩
5
Step 5
The cell at row $n$ and column $W$ gives the maximum obtainable value.

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
6
Step 6
Trace backward through the table to determine which items were included in the optimal subset.

Footnotes

0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩

Asymptotic Time Complexity Comparison

Relative growth by standard complexity class for major 0/1 knapsack approaches

(iv) Branch-and-Bound

Branch-and-bound is an exact method that explores the space of subsets as a decision tree, but avoids examining branches that cannot possibly beat the best solution found so far.2

Each node in the state-space tree represents a partial decision sequence over items:

left branch: include the next item,
right branch: exclude the next item.2

At each node, the algorithm computes:

current total weight,
current total profit,
an upper bound on the profit that could still be achieved from that node.2

If the upper bound is less than or equal to the best feasible profit already found, the node is pruned because no completion of that partial solution can improve the answer.2

A common upper bound is obtained by pretending the remaining problem is fractional knapsack:

continue adding remaining items in descending value-to-weight ratio,
allow the last item to be added fractionally,
use the resulting value as an optimistic bound.2

This works because allowing fractional items can only increase the achievable value, so it safely overestimates what is possible in the 0/1 setting.2

Time complexity

Worst-case time is still exponential, typically $O(2^n)$ , because in the worst case the algorithm may need to explore most of the tree.2 However, good bounds and good item ordering can dramatically reduce the number of visited nodes in practice.2

Limitations

Branch-and-bound is highly instance-dependent.2 On favorable instances it is much faster than brute force; on unfavorable ones, pruning is weak and exponential behavior returns. It also requires more implementation care than brute force or standard DP.

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹ ↩¹⁰ ↩¹¹

Branch-and-Bound Procedure

1
Step 1
Arrange items in nonincreasing order of $v_i/w_i$ , which improves the quality of the fractional upper bound.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
2
Step 2
Begin with no items chosen, profit $0$ , weight $0$ , and compute an optimistic bound.

Footnotes

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
3
Step 3
Create one child that includes the next item and another that excludes it.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
4
Step 4
Whenever a feasible node has better profit than the current best solution, record it as the new incumbent.

Footnotes

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
5
Step 5
Estimate the best possible completion of each child using the fractional-knapsack-style upper bound.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
6
Step 6
Discard any node whose bound is not better than the incumbent, because it cannot lead to an improved solution.2

Footnotes

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩
7
Step 7
When all promising nodes have been explored or pruned, the incumbent is the optimal solution.

Footnotes

The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩

The branch-and-bound search can be pictured as follows:

The major idea is not to avoid exact search entirely, but to make exact search selective.2 This distinguishes branch-and-bound from brute force:

brute force explores everything,
branch-and-bound explores only nodes that still look capable of producing the optimum.2

Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩²
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩ ↩²

Approach-by-Approach Clarifications

Exam-Ready Insight

For 0/1 knapsack, the most important conceptual contrast is: greedy is fast but not guaranteed optimal, while dynamic programming and branch-and-bound are exact methods.4

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩

Comparative synthesis

The four methods can now be contrasted more precisely.

Method	Main idea	Optimal?	Time complexity	Strength	Weakness
Brute force	Try every subset	Yes	$O(2^n)$	Simple and exact	Intractable for large $n$
Greedy	Pick locally best items by rule	No	Usually $O(n \log n)$	Fast and easy	Can miss best subset
Dynamic programming	Fill a table of subproblems	Yes	$O(nW)$	Exact and systematic	Large $W$ causes high cost
Branch-and-bound	Tree search with pruning	Yes	Worst case $O(2^n)$	Often far less search than brute force	Heavily data-dependent

A concise conclusion is:

Brute force is the baseline exact method.2
Greedy is a heuristic and fails because 0/1 choices make local decisions irreversible.2
Dynamic programming is the classic exact algorithm with pseudo-polynomial complexity.2
Branch-and-bound remains exact while reducing search through intelligent pruning.2

From a design perspective, the greedy method fails not because sorting by ratio is unreasonable, but because the structure of 0/1 knapsack does not permit local decisions to safely stand in for global optimization.2

0-1 Knapsack Optimization with Branch-and-Bound Algorithm - Discusses brute force, greedy, dynamic programming, and branch-and-bound approaches with complexity comparisons. ↩
0-1 Knapsack Problem - InterviewBit - Provides recursive and dynamic programming formulations, including $O(2^n)$ brute force and $O(nW)$ DP complexity. ↩ ↩²
Comparing between different approaches to solve the 0/1 Knapsack Problem - Summarizes greedy strategies, their complexity, and why they do not guarantee optimality for 0/1 knapsack. ↩ ↩²
SI335: 0/1 Knapsack - Greed is bad - Notes that multiple greedy choices fail to always produce an optimal 0/1 knapsack solution. ↩ ↩²
Branch and bound: Method knapsack problem - MIT OpenCourseWare - Explains branch-and-bound for knapsack, including fractional upper bounds and worst-case behavior. ↩ ↩²
The 0-1 Knapsack problem via B&B - Covers state-space tree search, promising nodes, bounds, and best-first branch-and-bound ideas. ↩

Knowledge Check

Question 1 of 4

Q1Single choice

Which statement best explains why the greedy ratio method can fail for the 0/1 knapsack problem?

Because sorting items is too slow

Because 0/1 knapsack does not always satisfy the greedy-choice property

Because values must be negative for greedy to work

Because dynamic programming is always faster

Explore Related Topics

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size  $n$ , explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

Best case: $T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I)$ , the minimum time over all inputs of size  $n$ .
Worst case: $T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I)$ , giving a guaranteed upper bound.
Average case: $T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I)$ , requiring an explicit input probability model.
Linear search illustrates the three cases: $\Theta(1)$ best, $\Theta(n)$ worst, and $\Theta(n)$ average (expected $\frac{n+1}{2}$ comparisons).
Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

The lesson shows how dynamic programming determines the cheapest way to multiply the matrix chain with dimensions  $\{4,10,3,12,20,7\}$ .

The recurrence $m[i,j]=\min_{i\le k<j}\big(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\big)$ with $m[i,i]=0$ computes optimal sub‑costs.
Filling the cost table yields $m[1,5]=1344$ , and the split table gives the top‑level split $k=2$ .
The optimal parenthesization is  $(A_1A_2)\big((A_3A_4)A_5\big)$ , requiring $120+720+420+84=1344$ scalar multiplications.
The bottom‑up algorithm runs in $O(n^3)$ time and uses $O(n^2)$ space.

Solving the Recurrence $T(n)=T(n-1)+n$ by Substitution Method

The course shows how to solve the decrease‑by‑one recurrence (T(n)=T(n-1)+n) (with (T(1)=1)) using the substitution method.

Repeatedly substitute (T(n-i)=T(n-i-1)+(n-i)) until reaching the base case, yielding (T(n)=T(1)+2+3+\dots+n).
The resulting sum is the triangular number (\frac{n(n+1)}{2}).
The dominant term (\frac{1}{2}n^{2}) gives a tight asymptotic bound (\Theta(n^{2})).
For recurrences of the form (T(n)=T(n-1)+f(n)), expanding to a summation quickly reveals the closed form.

Browse all research articles

Solving the 0/1 Knapsack Problem: Brute Force, Greedy, Dynamic Programming, and Branch-and-Bound

AI Summary

Footnotes

0/1 Knapsack - Two Methods - Dynamic Programming

Core Distinction

Footnotes

Problem intuition and evaluation criteria

Footnotes

Conceptual Roadmap for Solving 0/1 Knapsack

Model the decision

Footnotes

Try direct enumeration

Footnotes

Use local heuristics

Footnotes

Exploit subproblem structure

Footnotes

Prune the search

Footnotes

(i) Brute-force method

Time complexity

Limitations

Footnotes

Brute-Force Walkthrough

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Why brute force scales poorly

Footnotes

(ii) Greedy method

Time complexity

Why greedy may fail

Limitations

Footnotes

Footnotes

Footnotes

(iii) Dynamic Programming

Time complexity

Space complexity

Limitations

Footnotes

Dynamic Programming Table Construction

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Asymptotic Time Complexity Comparison

(iv) Branch-and-Bound

Time complexity

Limitations

Footnotes

Branch-and-Bound Procedure

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Footnotes

Approach-by-Approach Clarifications

Exam-Ready Insight

Footnotes

Comparative synthesis

Footnotes

Knowledge Check

Explore Related Topics