# 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})$

How to think of the problem

Think of it like a bag of coins, where each coin has a weight, but each coin also has value ($1,$2, etc). You want to maximize the bag’s value while staying within the constraints of the weight.

Resources

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

0-indexed

In CS341, we saw a 1-indexed version, which to me is more intuitive

- The reason 1-indexed is much easier is because we have space for the base case. In the example above, we use 1-indexed for dp, but 0-indexed for the actual values, which makes it super confusing
**So in general, just use 1-indexed!!**- The issue is that arrays are generally 0-indexed if they already give it to you, which makes it kind of annoying

more generally

I find that 1-indexed is easier, due to setting up the base case at

`i==0`

.

1-indexed solution

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: