Design and Analysis of Algorithms208110 marksNumerical: Fractional knapsackGreedy Algorithms
Does greedy algorithm guarantee optimal solution? Solve the Fractional knapsack problem to find maximum loot from given information. | Item | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | Value | 12 | 10 | 20 | 15 | 2 | 3 | 50 | | Weight (kgs) | 2 | 1 | 3 | 2 | 12 | 10 | 1 |
Does greedy algorithm guarantee optimal solution? Solve the Fractional knapsack problem to find maximum loot from given information.
| Item | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Value | 12 | 10 | 20 | 15 | 2 | 3 | 50 |
| Weight (kgs) | 2 | 1 | 3 | 2 | 12 | 10 | 1 |
[10]
Item 1 2 3 4 5 6 7 --------------------------- Value 12 10 20 15 2 3 50 Weight (kg) 2 1 3 2 12 10 1 Missing data: The knapsack capacity $W$ is not given in the problem. This is essential to solve the fractional knapsack. This solution assumes $W = 15$ kg, which must be flagged as an assumption. -...