These problems are very interesting and very much researched for much efficient solutions.

Try your hand at them.

1. Maximum Value Contiguous Subsequence. Given a sequence of n real numbers A1 . . .An, determine

a contiguous subsequence Ai . . .Aj for which the sum of elements in the subsequence is maximized.

2. Making Change. You are given n types of coin denominations of values v1 <>

integers). Assume v1 = 1, so you can always make change for any amount of money C. Give an algorithm

which makes change for an amount of money C with as few coins as possible.

3. Longest Increasing Subsequence. Given a sequence of n real numbers A1 . . .An, determine a subsequence

(not necessarily contiguous) of maximum length in which the values in the subsequence form a

strictly increasing sequence.

4. Box Stacking. You are given a set of n types of rectangular 3-D boxes, where the ith box has height hi,

width wi and depth di (all real numbers). You want to create a stack of boxes which is as tall as possible,

but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are

each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that

any side functions as its base. It is also allowable to use multiple instances of the same type of box.

5. Integer Knapsack Problem (Duplicate Items Forbidden). This is the same problem as the example

above, except here it is forbidden to use more than one instance of each type of item.