ADA: Greedy Technique - Fractional Knapsack

Fractional Knapsack

Knapsack is a problem in in which a thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items available in the store and weight of i^th item is w_i and its profit is p_i. What items should the thief take?

In this context, the items should be selected in such a way that the thief will carry those items for which he will gain maximum profit. Hence, the objective of the thief is to maximize the profit.

Knapsack problems are categorized as

• Fractional Knapsack
• 0-1 Knapsack

In fractional knapsack items are generally broken into smaller pieces, hence the thief can select fractions of items.

Problem Statement

A thief considers taking 100 pounds of loot. The loot is in the form of 5 items,
each with weight wi and value vi. Any amount of an item can be put in the
knapsack as long as the weight limit 100 is not exceeded.

W: 10  20  30  40  50

V:  20  30  66  40  60

Output

File: Download here