Virtual Labs

Greedy Algorithms 2: Fractional Knapsack Problem

What is the main objective of the knapsack problem?

a: To minimize the number of items selected Explanation

Explanation

b: To maximize the total value without exceeding capacity Explanation

Explanation

c: To maximize the total weight of items Explanation

Explanation

d: To select all available items Explanation

Explanation

What is the main idea behind the greedy approach used in the Fractional Knapsack problem?

a: Select items with the highest weight first Explanation

Explanation

b: Select items randomly until capacity is filled Explanation

Explanation

c: Select items with the highest value-to-weight ratio first Explanation

Explanation

d: Select items with the lowest value first Explanation

Explanation

Among the following operations, which operation is performed first in the Fractional Knapsack algorithm?

a: Fill the knapsack randomly Explanation

Explanation

b: Sort items by value-to-weight ratio Explanation

Explanation

c: Select the heaviest item first Explanation

Explanation

d: Calculate total weight of all items Explanation

Explanation

What does the value-to-weight ratio of an item represent?

a: Value gained per unit weight Explanation

Explanation

b: Total weight of the item Explanation

Explanation

c: Total profit of the item Explanation

Explanation

d: Remaining capacity of the knapsack Explanation

Explanation

Why is sorting required in the Fractional Knapsack algorithm?

a: To arrange items by increasing weight Explanation

Explanation

b: To arrange items by decreasing value Explanation

Explanation

c: To remove duplicate items Explanation

Explanation

d: To prioritize items with higher value-to-weight ratio Explanation

Explanation

What happens when an item does not completely fit into the remaining knapsack capacity in Fractional Knapsack?

a: The item is skipped Explanation

Explanation

b: The knapsack is discarded Explanation

Explanation

c: A fraction of the item is taken Explanation

Explanation

d: The algorithm stops without adding value Explanation

Explanation

Which property makes the greedy approach optimal for Fractional Knapsack?

a: Overlapping subproblems Explanation

Explanation

b: Greedy choice property Explanation

Explanation

c: Recursive structure Explanation

Explanation

d: Exhaustive search Explanation

Explanation

Which of the following constraints must always be satisfied in the knapsack problem?

a: Total weight must not exceed capacity Explanation

Explanation

b: Total weight must exceed capacity Explanation

Explanation

c: Total value must be minimized Explanation

Explanation

d: All items must be selected Explanation

Explanation

Which of the following is an application of the Fractional Knapsack problem?

a: Finding shortest path in a graph Explanation

Explanation

b: Sorting a list of numbers Explanation

Explanation

c: Cargo loading and resource allocation Explanation

Explanation

d: Searching in a database Explanation

Explanation

What type of problem is the Fractional Knapsack problem classified as?

a: Decision problem Explanation

Explanation

b: Searching problem Explanation

Explanation

c: Sorting problem Explanation

Explanation

d: Optimization problem Explanation

Explanation