Question

1. 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

2. 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)

3. 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])

4.

Complexity of Knapsack Problems

Which of the following versions of the Knapsack Problem can be solved (optimally) in polynomial time?

Multiple answers:You can select more than one option

A) Fractional Knapsack Problem

B) 0/1 Knapsack Problem

C) 0/1 Knapsack Problem with integer knapsack capacity

D) none of the above

Please, include a short explanation with the answer.