You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
notes/classes/algorithms/knapsack_problem.md

1.6 KiB

Knapsack Problem

Date: 04-05-22

Class: algorithms


given a bag with a known capacity *W*, and items with known weights *w* and values *v*, the knapsack problem attempts to reach the bags capacity with the largest possible value

To start solving a complex problem like this, we need to form a useful recurrence_relations, that allows us to break down the problem into smaller subproblems. In this case, the answer is

$$ V (i ,j ) = max \ {vi + V (i − 1,j − wi ),V (i − 1,j )} $$ where i is the number of items, and j is the wieght that the bag can hold.

This is solved by approaching it as if it were a table, and using dynamic_programming_basics to store the solutions

r:items c:size 0 1 2 3 4 5 6
pyramid (w2,v10) 0 0 10 10 10 10 10
totem (w1,v7) 0 7 10 17 17 17 17
orb (w4,v25) 0 7 10 17 25 32 35
canister (w3,v20) 0 7 10 20 27 32 37
lamp (w2,v15) 0 7 15 20 27 35 42

By checking adjacent solutions, we can compare the value of the previous weighted bag, and this one, to assemble a bag of a larger total value

by using dynamic_programming_basics we have turned this from an exponential problem to $$O(nm)$$ where n = the number of items, and m = the weight

see also

list without id file.inlinks
where file.name = this.file.name