What greedy selection criteria provides an optimal solution to the fractional knapsack problem?
Show answer
Highest value-to-weight ratio
For the fractional knapsack, you can take items based on their value-to-weight ratio (density). For the 0-1 knapsack, this greedy approach fails, and dynamic programming is required to find the optimum.
Also asked as:
- To solve the fractional knapsack problem optimally using a greedy approach, what property of the items should be used for selection?