Algorithm Design and Problem Solving

Project 8: Knapsack problem

Hand-out: 2.11., deadline: 22.11.

Story: By your dauntlessness and abilities you defeated a weird magician and now you can take a princess (ladies version: a prince) or to take away something of beautiful precious jewelry owned by the magician. As you do not like the princess (ladies version: a prince), you decided to take the gold. You can take a plenty of marvelous and big objects, the only condition is that the chosen objects must be carried out in a knapsack whose capacity is limited (and yours as well, after all). If you do not succeed, you will gain nothing. Objects are various – jewelry, statues, candle sticks ..., each has a different value and a different weight. Now you can utilize your knowledge of dynamic programming from ADE.

Your task based on this story is as follows:

Input is a set of items P={p₁,p₂,...,p_n}, where the item p_i has a size s_i and a value v_i, knapsack capacity is C. Your task is to find a subset with a maximal value found as a sum of values of subset items such that the sum of sizes of items in the subset does not exceed C (i.e., all selected items must fit into the knapsack). Sizes and values are positive integers less than or equal to 1000.

1. Solve this problem by a clear, simple and correct greedy algorithm for 3 points.
2. Solve this problem by a correct algorithm based on dynamic programming for 8 points.