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.

# 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

``````list without id file.inlinks