Knapsack Problems

Nowdays I'm studying recursion, dynamic programming, solved some problems on it. There's this particular problem I was studying on, its called the knapsack problem.

I had so much trouble solving some knapsack problems, some were easy, some were clear to me but i couldnt solve them, later found that those problems were not of the same type even though they sound similar and i was constantly trying to tackle them with the same method.. Failed doing so. So I thought there must be some general types of knapsack problems. I did some googling and found that there are atleast six types of knapsack problems.

Knapsack problem is a name to a family optimization problems that have the following general theme: You are given a knapsack with a maximum weight/ capacity, and you have to select a subset of some given items such that a profit sum is maximium, without exceeding the capacity of the knapsack.

Further learnt that knapsack problem is a NP-hard problem. NP is a complexity class of computational problems and NP hard is the hardest among all the NP problems. Sounds scary right?, I think that  explains why most DP problems have so small constraints. The easiest method to solve this problems is Dynamic Programming , which solves these problems in pseudo polynomial time.


Types of Knapsack problems;

1. 0/1 knapsack problem : most basic type, given a knapsack with a maximum weight, and you have to select a subset of some given items such that a profit sum is maximized without exceeding the capacity of the knapsack.
2. Number partitioning : Partition a set S containing N integers, into two sets S1 and S2, so that |sum(L1) - sum(L2)| is minimized. This problem is perhaps even more general than the 0/1 knapsack problem and is one of the six basic NP-hard problems.
3. Bounded Knapsack : Instead of N items, you are given M types of items, each type having a bounded quantity.
4. Unbounded Knapsack : You have an unbounded quantity of each item type, instead of a bounded quantity.
5. Multiple Knapsack problem: same as the 0/1 knapsack problem but you are given multiple knapsacks of different sizes. The capacity constraint must be met for all of the knapsacks.
6. Box-packing problem : Also called as The Bin-packing problem. You have some number of equally sized bins. You need to pack the items into bins so that the number of bins used is as small as possible.

Each of this problem have different variations too. For example the 0/1 knapsack problem covers the following problems:

(i) Subset sum problem
(ii) Equal sum partion
(iii) Count of subset
(iv) Minimum subset sum
(v) Target sum

and lot more...


I understand knapsack problem much better now. And I'm confident and excited to solve newer variations of Knapsack problem or atleast similar problems just for fun. Will be posting about the problems with solutions.