SE250:May 30
Jump to navigation
Jump to search
Notes
Some notes about the implementation of the Knapsack Problem.
v1 = 7, w1 = 3
v2 = 4.5 w2 = 2
v3 = 1 w3 = 1
W = 7
We need to generate all possibilities in the worst case and then prune it. It implicitly has a variable Xi which is equal to the number of type i chosen. We have to maximize the total value. Total value = sum of Xi x vi
Sum of Xi x wi <= W
Heres a link to the Knapsack Problem on Wikipedia: