Question

Fractional Knapsack Problem Algorithm

which best describes the tightest range of the number of items with only fractional inclusion (i.e. not entirely included or excluded) in the knapsack? (Let n denote the number of items for possible inclusion.)

A) At least 0 items and at most n items

B) At least 1 items and at most n items

C) Exactly n items

D) At least 0 items and at most n-1 items

E) At least 1 items and at most n-1 items

F) At least 0 items and at most 1 items

G) Exactly 1 items

H) Exactly 0 items

Fractional Knapsack Problem - Time Complexity

Assuming that the values per weight can be represented with no more than three digits each before and after the decimal point, which best describes the TOTAL time complexity of our greedy algorithm for the Fractional Knapsack Problem?

A) Θ(log n)

B) Θ(n)

C) Θ(n log log n)

D) Θ(n log n)

E) Θ( n^2)

F) Θ(n^2 log n)

Fractional Knapsack Algorithm- Fractional Case

In the greedy algorithm for the Fractional Knapsack Problem, what should go in the blank to determine the fraction being used?

A) fraction = initialCapacity / value[i]

B) fraction = initialCapacity / weight[i]

C) fraction = initialCapacity / (value[i]/weight[i])

D) fraction = remainingCapacity / value[i]

E) fraction = remainingCapacity / weight[i

F) fraction = remainingCapacity / (value[i]/weight[i])

Answer 1

1) B) At least one item and at most n items

At least one item --- because at least a fraction of the item can be included.

At most n items --- because we can include the fraction of all the items

2) D) Θ(n log n) --- Time complexity is Θ(n log n)

3) F) fraction = remaining capacity / (value[i]/weight[i])

Because we need the remaining capacity to get the fraction

and value and weight of the item is important to calculate the fraction

value/weight gives a factor which can be used to calculate the fraction