SE250:May 30

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:

Knapsack Problem