際際滷

際際滷Share a Scribd company logo

0/1Knapsack

P
Pradhan Rishi Sharma

The document discusses the 0/1 knapsack problem and different approaches to find the optimal solution. It describes the problem as filling a knapsack from objects with given weights and benefits to maximize the total benefit within a weight limit. It then summarizes dynamic programming and greedy approaches to solve the problem, and shows the optimal solution is to choose items with weights 3, 4, and 5 to get a total benefit of 9 within the weight limit of 7.

1 of 10
Downloaded 10 times
0/1 Knapsack Problem and Optimal merge pattern
The Problem: We have a knapsack to be filled with enlisted objects of given weight and benefit ,total weight=7 find the optimal merge pattern to do so . WEIGHT: 1 3 4 5 BENEFIT: 1 4 5 7
Approaches to solve the problem The Greedy approach:Make the locally optimal choice at each stage with the hope of finding a global optimum. The brute-force approach:It is a trial and error method used to find global optimum.(i.e Compute all possible combinations and search for optimal) The Dynamic Programming approach:Formula is to break a large problem down into small sub steps so that, at any given stage, optimal solutions are known to sub-problems. The 4th approach: Discussed at the end of presentation.
Benefit Weight 0 1 2 3 4 5 6 7 1 1 4 3 5 4 7 5
If total weight is zero , no matter what i have the max benefit would still be zero. Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 4 3 0 5 4 0 7 5 0
Even though the total weight is high all i have is 1 item so max is 1 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 5 4 0 7 5 0
Max(4+1 or 1),hence 5 max(4+0 or 1), hence 4 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 7 5 0
Max(5+4 or 5), hence 9 max(7+1 or 6),hence 8 Max(7+1 or 9),hence 9 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 5 6 6 9 7 5 0 1 1 4 5 7 8 9
The 4th approach :solves problem through machine learning(i.e)study of pattern recognition and computational learning theory. Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 5 6 6 9 7 5 0 1 1 4 5 7 8 9
Thank you !

More Related Content

0/1Knapsack

  • 1. 0/1 Knapsack Problem and Optimal merge pattern
  • 2. The Problem: We have a knapsack to be filled with enlisted objects of given weight and benefit ,total weight=7 find the optimal merge pattern to do so . WEIGHT: 1 3 4 5 BENEFIT: 1 4 5 7
  • 3. Approaches to solve the problem The Greedy approach:Make the locally optimal choice at each stage with the hope of finding a global optimum. The brute-force approach:It is a trial and error method used to find global optimum.(i.e Compute all possible combinations and search for optimal) The Dynamic Programming approach:Formula is to break a large problem down into small sub steps so that, at any given stage, optimal solutions are known to sub-problems. The 4th approach: Discussed at the end of presentation.
  • 4. Benefit Weight 0 1 2 3 4 5 6 7 1 1 4 3 5 4 7 5
  • 5. If total weight is zero , no matter what i have the max benefit would still be zero. Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 4 3 0 5 4 0 7 5 0
  • 6. Even though the total weight is high all i have is 1 item so max is 1 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 5 4 0 7 5 0
  • 7. Max(4+1 or 1),hence 5 max(4+0 or 1), hence 4 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 7 5 0
  • 8. Max(5+4 or 5), hence 9 max(7+1 or 6),hence 8 Max(7+1 or 9),hence 9 Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 5 6 6 9 7 5 0 1 1 4 5 7 8 9
  • 9. The 4th approach :solves problem through machine learning(i.e)study of pattern recognition and computational learning theory. Benefit Weight 0 1 2 3 4 5 6 7 1 1 0 1 1 1 1 1 1 1 4 3 0 1 1 4 5 5 5 5 5 4 0 1 1 4 5 6 6 9 7 5 0 1 1 4 5 7 8 9