The Knapsack Problem Flashcards
1
Q
What is the Knapsack Problem
A
It is a combinatorial optimization problem that aims to maximize the total value of items placed in a knapsack of limited capacity.
2
Q
What is the recurrence relation used in a knapsack problem
A
K(i,w) = {
0 iff i = 0 or w = 0,
K(i-1, w) if wi > w,
max( K(i-1, w-w), [vi + K(i-1, w-wi)])
}
* where i K(i,w) represents the maximum value of the items that can be placed in the knapsack for the first ith items
* w is the capacity of the knapsack
* wi is the weight of the ith item
* vi is the value of the ith item
3
Q
Solve an example.
A
Ask Ai to give you an example to solve
4
Q
What is the time complexity of the Knapsack problem?
A
O(nW)
5
Q
What is the space complexity of the Knapsack problem?
A
O(nW)
