Brute-Force Knapsack and the Exponential Power Set

Why does checking every subset solve the 0/1 knapsack perfectly, yet become hopeless at just 100 items?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Let the 0/1 vector select the value

Four items have values values = [60, 100, 120, 30], and the choice vector is V = [1, 0, 1, 1]. Compute the objective from the video, $\sum_i V[i] \cdot \text{value}_i$ , so that each value is multiplied by its bit. You may find zip() and sum() useful. Assign the result to total_value.

values = [60, 100, 120, 30]
V = [1, 0, 1, 1]
total_value = ...  # your code here

values = [60, 100, 120, 30]
V = [1, 0, 1, 1]
total_value = ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

is an integer

counts only the items whose bit is 1

←Previous Optimization Models and the Knapsack Problem Next Greedy Algorithms: One Function, Any Definition of Best →