ADA: Dynamic Programming - 0/1 Knapsack

0/1 Knapsack

Knapsack is a problem 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 0-1 Knapsack, items cannot be broken which means the thief should take the item as a whole or should leave it. This is a reason behind calling it as 0-1 Knapsack.

Problem Statement

A thief considers taking 8 pounds of loot. The loot is in the form of 4 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 8 is not exceeded.

• Value: { 15, 10, 9, 5}
• Weight: { 1, 5, 3, 4 }

Output:

File: Download here