CT243 lab4
http://geminga.it.nuigalway.ie/~gettrick/courses/CT243/labs/l4.html
-
For this lab you must submit
-
Handwritten development notes, including statement of the problem, analysis of the problem, algorithm design (which may include flow charts).
-
A printout of form, image and code of your program, and any numerical answers requested.
-
The above material should be given to David or left in the cardboard box marked CT243 in the mail room (room IT415) on the 4th floor of the IT Building
before
the deadline of 5pm
Monday 25th February 2008. You will lose 20% for each day
(or part of day) the lab is late.
Consider a Knapsack problem where we have ten (10) items with weights
[12,17,5,3,17,10,14,10,9,4] (in Kg) and values
[36,50,12,10,55,27,45,30,25,13] (in euro) respectively. (You can
call these items A, B, C, ...,J if you want....) There is only one of
each item.
-
Let the bag/knapsack capacity K be 60 Kg. Write a program in VB .net to
solve this problem (i.e. decide which items to put in to the bag
to achieve maximum value) using a brute force technique. Using this technique
you should consider all possible options, i.e.
-
Ways of choosing one item: i.e. just A, or just B, or...
-
Ways of choosing two items: i.e. AB or AC or AD or... or BC or BD or...
-
Ways of choosing three items: i.e. ABC or ABD or ABE or... or ACD or ACE or...
-
etc.
Hint:
One way to do this would be to create a new array with 10 elements, with
each element 1 or 0: 1 means "choose the object". So
[1,0,0,0,0,1,1,0,0,0] corresponds to choosing AFG. There are
210 = 1,024 possible choices. For each one of these (if it
is not over the bag capacity) determine the value, and keep a running
total of the current maximum value.
-
Write a separate program (or just a different function) to "solve" the
problem using the greedy strategy "at each step, pick next lightest item".
Do you get the same answer as in (1.)?
-
Write down the solution to the problem if the bag capacity is
-
68kg
-
49kg
©
NUI, Galway