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_{1},p_{2},...,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.

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