November 6th - 0/1 Knapsack Algorithm, Stack of Blocks Problem

Example 2D Solution Matrix:
Max Weight = 5

Size of the Array = [Max Weight][Number Of Items]
0 0 0 0 0
0 0 1 1 1
0 0 1 7 7
0 0 1 7 9

The optimum value can be found in the bottom right corner of the array.

To find the value of entry (k, item index)
if (k < weight)
value of entry = value of entry directly above
else if (k==weight)
value of entry = max(value above this entry, value of the item being examined)
else if (k>weight)
value of entry = max(value above this entry, value of the item in the row above this entry's with it's x position equal to k minus the weight of this item)

If you're still confused, try checking out this site:
http://jhave.org/learner/misc/knapsack/knapsack.shtml

It also explains how to find which elements are included in the optimal solution.

Given:
max weight: int c
weights: int []a
values: int []b

Find:
The largest value that can fit into the bag

Remember: The first row in the 2-D array should be filled with 0s!

Stacks of Blocks
Some kids play with blocks, and build things by stacking different blocks on top of each other. Given a set of blocks and a target height, we want to find out the largest size of a stack built out of the blocks less than or equal to a target height.

The input file DATA4.txt will contain at least 3 lines, one positive integer value per line. The first line will contain an integer H, the target height for the stack. 0 < H < 100

The second line will contain an integer S, number of blocks in a set. 0 < S < 10

The next S lines will contain integers, one per line; 0 < N < 10; representing the height of blocks in the set.

The output file OUT4.txt will contain a single integer value, the size of the largest possible stack made from the blocks.

Sample Input:
5
3
1
2
3

Sample Output:
5

Sample Input:
8
3
9
18
12

Sample Output:
0