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
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 (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 , determine all sums that can be constructed using the weights.
We can recursively calculate this using the recurrence
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: