Viva 1 - Fractional knapsack problem

Fractional knapsack problem is solved most efficiently by which of the following algorithm?

• Divide and conquer

• Dynamic programming

• Greedy algorithm

• Backtracking

What is the objective of the knapsack problem?

• To get maximum total value in the knapsack

• To get minimum total value in the knapsack

• To get maximum weight in the knapsack

• To get minimum weight in the knapsack

Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?

• In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible

• Both are the same

• 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming

• In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

The result of the fractional knapsack is greater than or equal to 0/1 knapsack.

• True

• False

Time complexity of fractional knapsack problem is

• O(n log n)

• O(n)

• O(n²)

• O(nW)