Homework 8 Solutions
1)
The goal is to fill the knapsack and maximize the total sum of values of the items
packed. Because fractions of items can be added, this problem can be solved with a
greedy approach. The basic idea is to balance the value of the item added with the size of
the item. The more valuable an item is, the more desirable it will be to add to the
knapsack. The value of the item can be computed as the value of the item divided by the
size of the item. To solve the fractional knapsack problem, simply calculate the value of
each item, sort the items by the value, and then add all of the most valuable, followed by
the second most, and so forth. At some point, either the knapsack will be full, in which
case the algorithm is done, or there will be no further items to add, or there will be more
of some item than there is space in the knapsack. Add the amount of this final item to the
knapsack required to fill the knapsack. This solves the fractional knapsack problem with
an O(n) scan to calculate the values, an O(n log n) sort, and an O(n) sort giving O(nlogn)
time.
Algorithm 1 [T] =fracKnapsack(K, S, V)
1: Input: K (the size of the knapsack), S (an array of size n storing both the sizes and
the values of elements being used to fill the knapsack
2: Output: A (a list of items containing the elements used to fill knapsack or a state-
ment stating that the knapsack can not be filled
3: begin
4: /* initialize the densities of each element to 0*/
5: for all elements e do
6: e:densit y = 0;
7: end for
8: /* calculate and store densities of each element */
9: for all elements e do
10: e:densit y = e:value=e:size;
11: end for
12: /*Sort the elements with respect to their density in descending order*/
13: /*you are able to use any fast sorting algorithms you know such as quicksort, or
even store them in a heap etc...*/
14: /*Initialize packed to 0, this variable represents how much of the knapsack is al-
ready packed*/
15: packed = 0;
16: /*Start from beginning of list, element should contain largest density*/
17: while packed < K and there are elements still in the list do
18: if e:size < K _ packed then
19: /*add element to the list containing the elements filling knapsack;*/
20: packed = packed +e:size;
21: else
22: /*calculate portion still needed to fill*/
23: portion = K _ packed;
24: /*change elements size to represent the size of element which as used*/
25: e:size = portion;
26: /*add element to the list containing the elements filling the knapsack;*/
27: packed = packed +e:size;
28: end if
29: end while
30: if packed = K then
31: return A;
32: else
33: /*Knapsack could not be filled;*/34: end if35: end
- 1
- 2
- 3
前往页