Knapsack Problem using Greedy Technique Example1 Method 1 | Lec 48 | Design & Analysis of Algorithm

Kanpsack Problem Definition
Given a Knapsack of capacity C/M and n items of weight {w1, w2, w3,…….wn} and profits {p1, p2, p3,…….pn}, the objective is to choose a subset of n objects that fits into the knapsack and that maximizes the total profit

GREEDY STRATEGY
Select the item with maximum profit that fits into the knapsack
Select the item with minimum weight that fits into the knapsack
Calculate Pi/Wi , select the item with maximum Pi/Wi

Knapsack Problem Design
Consider a knapsack with capacity C or M
Select the items from the list of n items with weight Wi and Profit Pi
Obtain solution such that
Sum of weights must not exceed knapsack capacity C
Optimal selection is object feasible and reaches maximum profit
The optimal solution is feasible object that reaches maximum profit
The problem can be stated as
Maximize ∑_(𝑖=1)^𝑛▒〖𝑃𝑖 𝑋𝑖〗
Subject to ∑_(𝑖=1)^𝑛▒〖𝑊𝑖 𝑋𝑖〗 ≤ C or M
with 0 ≤ 𝑋𝑖 ≤ 1, 1 ≤ 𝑖 ≤ n
The profits & weights are positive numbers

This video explains example to implement knapsack problem using Greedy Technique
Obtain the optimal solution for the knapsack problem using Greedy Method given the
Following
M = 40 Capacity of Knapsack
n = 3 number of objects
(w1, w2, w3) = (20, 25, 10) represents weights of 3 objects
(p1, p2, p3) = (30, 40, 35) represents profits of 3 objects



#knapsackproblem
#knapsackgreedytechnique
#greedymethod
#knapsackproblemusinggreedymethod
#knapsackexample
#greedytechnique
#cseguru
#shortestpathproblem
#csegurudaavideos
#cseguruadavideos
#singlesourceshortestpath
#designandanalysisofalgorithm
#ada
#daa


Binary Search Videos:
Binary Search:    • Binary Search General Method | Divide...  
Binary Search Technique Example 1:    • Binary Search Technique Example1 | Di...  
Binary Search Technique Example 2:    • Binary Search Technique Example 2 | D...  
Time complexity of Binary Search :    • Time complexity of Binary Search | Di...  


Quick Sort Videos
Quick Sort Design Steps:    • Quick Sort General Method | Divide & ...  
Quick Sort Example1:    • Quick Sort  Example1| Divide & Conque...  
Quick Sort Example2 :    • Quick Sort  Example2 | Divide & Conqu...  
Quick Sort Algorithm:    • Quick Sort  Algorithm | Divide & Conq...  

Merge Sort Videos
Divide & conquer :    • Divide and Conquer Technique | Master...  
Merge Sort Technique :    • Merge Sort General Method | Divide & ...  
Merge Sort Algorithm :    • Merge Sort Algorithm | Divide & Conqu...  
Time Complexity of Merge Sort :    • Time Complexity of Merge Sort | Divid...  

Bubble Sort Videos
Bubble Sort working Example | Brute Force |:    • Bubble Sort working Example |  Brute ...  
Bubble Sort Algorithm | Logic tracing with Example:    • Bubble Sort Algorithm Logic | Brute F...  

Selection Sort
Selection Sort | Algorithm Example & Analysis:    • Selection Sort Example & Analysis | B...  

CSEGuru Videos
#CSEGuru Compiler Design Videos:
   • Compiler Design  

CSEGuru DAA Videos
   • Design & Analysis of Algorithm  

CSEGuru Operating System Videos
   • Operating System  

CSEGuru Gate cse Videos
   • Gate cse  

CSEGuru NET cse Videos
   • NET cse  

CSEGuru Data Structure Videos
   • Data Structure  

CSEGuru Sorting Algorithm Videos
   • Sorting Algorithm