1. A thief enters a museum and want to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight.
Problem is to find the combination of artifacts thief takes so that he gets maximum value and weight of all the taken artifacts is less the capacity of the bag he has brought.
Thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0-1 knapsack.
2. Second flavor is : We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be store the re-computation cost is Vi. Problem is to store as files on storage that combined size of all files is less than W and their re-computation value is maximum.
2. Second flavor is : We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be store the re-computation cost is Vi. Problem is to store as files on storage that combined size of all files is less than W and their re-computation value is maximum.
We can either store or leave the file. We cannot store partial file. Hence this is a case of 0-1 knapsack problem.
In pure mathematics terms:
There are N items <I1,I2,................In> each having a weight <w1,w2,...............wn>.
Each item has a value associated with it <v1,v2, ..........vn>
Given a limit W we have to find a subset of K items such that
Sum (w1, w2..... wk) <= W &
Sum (v1,v2,.........vk) is maximum.
Read full article from Algorithms and Me: Dynamic programming : 0-1 knapsack problem
No comments:
Post a Comment