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

## 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

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.

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

**Dan**- Alumni
- Number of posts : 73

Age : 26

Location : Waterloo, Ontario

Grade : >12

L337ness :

Registration date : 2008-08-27

Similar topics

» Did you commit to Selenium-Stack Exchange site?

» Strack & Van Til Gift Card Giveaway *illinois and Indiana only*

» New Routing Algorithm in Mediacore

» Internet Explorer driver

» Ternak convict cichlid

» Strack & Van Til Gift Card Giveaway *illinois and Indiana only*

» New Routing Algorithm in Mediacore

» Internet Explorer driver

» Ternak convict cichlid

Page

**1**of**1****Permissions in this forum:**

**cannot**reply to topics in this forum