[Tutorial] Optimized solution for Knapsack problem

Revision en3, by sdnr1, 2018-05-21 16:23:38

Problem Statement

We are going to deal with the well known knapsack problem with an additional constraint in this blog. We are given a list of N items and a knapsack of size W. Every item has a cost ci associated with it (1 ≤ i ≤ N). We can select some items from the list such sum of the cost of all the selected items does not exceed W. The goal is tell for all w (1 ≤ w ≤ W), if we can select any number of items such that their total cost equals w. This is also known as the 0/1 knapsack problem. The addition constraint we have is .


The bounded knapsack problem

The bounded knapsack problem is like the 0/1 knapsack problem, except in this we are also given a count for each item. In other words, each item has a count si associated with it and we can select an item si times (1 ≤ i ≤ N).


Solving bounded knapsack problem

The solution is simple. Let dp[i][j] be the minimum count of ith item that has to be used to get a total cost of j while using some number(possibly 0) of first i items.

Tags #dp, knapsack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English sdnr1 2018-05-24 09:40:32 385
en8 English sdnr1 2018-05-22 22:02:49 17
en7 English sdnr1 2018-05-21 17:50:32 2 (published)
en6 English sdnr1 2018-05-21 17:45:34 25
en5 English sdnr1 2018-05-21 17:43:48 768
en4 English sdnr1 2018-05-21 16:42:51 460
en3 English sdnr1 2018-05-21 16:23:38 305
en2 English sdnr1 2018-05-21 15:58:49 12
en1 English sdnr1 2018-05-21 15:47:22 1023 Initial revision (saved to drafts)