# Knapsack Problem

The term knapsack refers to problems where a set of objects is given, and subsets with some properties have to be found. Knapsack problems can often be solved using dynamic programming.

Bottom-Up Knapsack (Iterative) in $O(n_{2})$

When we do bottom-up dp, we do it in Topological Order.

Note:
The example above uses 0-indexing. If you use 1=indexing, you should use `wt[i]`

instead of `wt[i-1]`

;
Notice I use for example `wt[i-1]`

, and when we `cin >> wt[i]`

its from `0...n-1`

. If you choose to do the update with `wt[i]`

, make sure to `cin 1...n`

, and then the update is for `wt[i]`

.

Optimized space. We need to go from `W...0`

because else the weights are going to be in different sizes.

#### Other Example

Given a list of weights $[w_{1},w_{2},...,w_{n}]$, determine all sums that can be constructed using the weights.

We can recursively calculate this using the recurrence $dp(x,k)=dp(x−w_{k},k−1)∨dp(x,k−1)$

However, here is a better implementation that only uses a one-dimensional array `possible[x]`

that indicates whether we can construct a subset with sum x.

The trick is to update the array from right to left for each new weight: