Knapsack Problem using Greedy Technique Example1 Method 1 | Lec 48 | Design & Analysis of Algorithm
11 هزار بار بازدید -
3 سال پیش
-
Kanpsack Problem DefinitionGiven a Knapsack
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
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
3 سال پیش
در تاریخ 1400/09/25 منتشر شده
است.
11,012
بـار بازدید شده