Knapsack Flashcards
1
Q
Describe the knapsack problem.
A
Given an empty set with capacity W (the knapsack) and a set of items with value v and weight w. What items can we choose to maximize sum(v_i) subject to sum(w_i)
2
Q
Describe the four construction methods centered around sorting the elements.
A
We can sort by weight ascending and descending, and by value ascending and descending.
We then select items while the weight limit of the knapsack hasn’t been reached yet.
3
Q
Describe how the greedy improvement heuristic can be used to improve this solution.
A
We can iteratively choose to swap two item from outside/inside the knapsack and calculate the resulting cost. If it’s better, keep the swap. If it’s worse, reject the swap. Repeat until some stopping criteria has been reached.
