November 6th  0/1 Knapsack Algorithm, Stack of Blocks Problem
Page 1 of 1 • Share •
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 2D 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.
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 2D 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 : 27
Location : Waterloo, Ontario
Grade : >12
L337ness :
Registration date : 20080827
Similar topics
» Did you commit to SeleniumStack Exchange site?
» New Routing Algorithm in Mediacore
» Ternak convict cichlid
» Senran Kagura Burst is coming to the North American 3DS eShop on November 14th!
» 1st November 1755  Lisbon earthquake
» New Routing Algorithm in Mediacore
» Ternak convict cichlid
» Senran Kagura Burst is coming to the North American 3DS eShop on November 14th!
» 1st November 1755  Lisbon earthquake
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum

