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.

####
1.6 KiB

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
```