Solving 0/1 Knapsack problem using greedy technique
Curious case of success of greedy method for fractional knapsack
Difference between greedy vs dynamic programming?
The Knapsack problem is a classic optimization problem where the goal is to select items, each with a weight and a value, to maximize the total value while keeping the total weight within a given limit (the capacity of the knapsack). One approach to solving this problem is using the Greedy Method, which makes locally optimal choices at each step in the hope of finding a global optimum.
The Greedy Method works by iteratively selecting the best feasible item to include in the knapsack at each step, based on a specific criterion, until the knapsack reaches its capacity. There are two variations of the Knapsack problem: 0/1 Knapsack and Fractional Knapsack. The Greedy Method can be applied differently to both variations.
Explanation of 0/1 Knapsack problem
Imagine a thief who’s planning to steal from a store. This store has n different items, each with its own value (how much money it’s worth) and weight (how heavy it is). The thief has a knapsack, a bag of sorts, that can only hold a maximum weight of W pounds.
The goal here is to figure out which items the thief should steal to get the maximum value from the store while not exceeding the weight limit of the knapsack. There’s a catch though: for each item in the store, the thief can only make one decision—either take the item and put it in the knapsack or leave it behind. The thief can’t take a part of an item, take an item more than once, or split items. It’s an all-or-nothing choice for each item.
The task for the thief is to figure out the best combination of items to steal, considering their values and weights, that will give them the highest total value without going over the weight limit of the knapsack. This problem is called the 0-1 knapsack problem because the thief has to make binary decisions for each item: either take it (1) or leave it (0).
So, the big question for the thief is: which items should be taken from the store to maximize the total value of loot without the total weight exceeding W pounds?
Fig a,b,c: for a thief limited to carrying 50 pounds, the optimal choice among three items is taking 2 and 3, not 1, despite 1 having the highest value per pound. In this 0-1 knapsack problem, the greedy strategy fails, unlike in the fractional knapsack where choosing by value per pound works optimally.
Imagine you’re a thief trying (See above Fig) to fill your bag with the most valuable items from a store, but your bag can only hold up to 50 pounds. There are three items you’re eyeing:
Item 1: It weighs 10 pounds and is worth $60. So, for each pound it weighs, it’s worth $6.
Item 2: This one is heavier, weighing 20 pounds, but it’s worth $100. So, for each pound, it’s worth $5.
Item 3: The heaviest of the three, weighing 30 pounds, but it’s worth $120. This means for each pound, it’s worth $4.
If you follow a simple rule of picking the item that’s worth the most for each pound it weighs, you’d think to grab Item 1 first because for every pound it weighs, it’s worth the most money ($6 per pound).
However, surprise! The best way to fill your bag and get the most money isn’t by following this simple rule. It turns out that if you grab Item 1 first, you won’t end up with the most money. The smarter move is to actually take both Item 2 and Item 3, leaving Item 1 behind.
Even though Item 1 seems like the best choice initially because it’s worth the most for its weight, doing this actually makes you miss out on the most money. So, following that simple rule doesn’t always lead you to the best outcome. In this case, taking both Item 2 and Item 3 together gives you the most money, even though individually they might not seem as efficient based on their value per pound.
On the contrary, (Fig-c) consider fractional knapsackproblem. In this scenario, you can take fractions of items (like cutting a cake). The strategy of selecting the most valuable item first (greedy strategy) works fine because you can take parts of an item to optimize the value.
Decision Making in the 0-1 knapsack Problem:
In the 0-1 problem, when deciding whether to put an item in the knapsack, you need to compare two possibilities:
One where you include the item and see how that affects the total value and space left.
Another where you exclude the item and check how the absence impacts the total value and space left.
This way of evaluating the choices helps in making the best decision on whether to include an item or not, considering the limited space and maximizing value.
The key difference lies in whether you can take fractions of items or only whole items, which affects how you strategize to fill the knapsack optimally.
