0–1 Knapsack in the bottom-up approach
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Why 0–1? It means if you want to pick any particular item, you have to take the whole amount. In the above image, we have a 2Kg items, we can not take 1Kg from that.
Another similar way to explain it-We have computed n data files that we want to store, and we have available W bytes of storage. The file i has size Wi bytes and takes Vi minutes to recompute. We want to avoid as much recomputing as possible, so we want to find a subset of files to store such that The files have combined size at most W . The total computing time of the stored files is as large as possible. We can not store parts of files, it is the whole file or nothing.
There are multiple ways to solve this problem, in this article, we will solve it by using DP with the bottom-up approach. Our knapsack size is W, we have to make maximum value to fill the knapsack. A simple approach will be, how can we get maximum value if your knapsack size 1, then compute maximum value if knapsack size is 2 and so on…W.
