Knapsack Problem

def. Knapsack Problem. You have items $0\dots n-1$ with costs $c[0\dots n-1]$ and utility $v[0\dots n-1]$ with a budget $B$. What is the maximum utility you can achieve? Course Description

Idea: Simple iteration DP

thm. Knapsack is NP-complete

• Idea: Reduce from Partition Problem.