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
2. Find the optimal solution to the knapsack instances
M = 15
n = 7
(p1, p2, p3 , p4, p5 , p6, p7) = (10, 5, 15, 7, 6, 18, 3)
(w1, w2, w3 , w4, w5 , w6, w7) = (2, 3, 5, 7, 1, 4. 1)
Reference Links
Knapsack Problem using Greedy Technique Introduction
• Knapsack Problem using...
Knapsack Problem using Greedy Technique Example1 Method 1
• Knapsack Problem using...
Knapsack Problem using Greedy Technique Example1 Method 2
• Knapsack Problem using...
#knapsackproblem
#knapsackgreedytechnique
#greedymethod
#knapsackproblemusinggreedymethod
#knapsackexample
#greedytechnique
#cseguru
#shortestpathproblem
#csegurudaavideos
#cseguruadavideos
#singlesourceshortestpath
#designandanalysisofalgorithm
#ada
#daa
Binary Search Videos:
Binary Search: • Binary Search General ...
Binary Search Technique Example 1: • Binary Search Techniqu...
Binary Search Technique Example 2: • Binary Search Techniqu...
Time complexity of Binary Search : • Time complexity of Bin...
Quick Sort Videos
Quick Sort Design Steps: • Quick Sort General Met...
Quick Sort Example1: • Quick Sort Example1| ...
Quick Sort Example2 : • Quick Sort Example2 |...
Quick Sort Algorithm: • Quick Sort Algorithm ...
Merge Sort Videos
Divide & conquer : • Divide and Conquer Tec...
Merge Sort Technique : • Merge Sort General Met...
Merge Sort Algorithm : • Merge Sort Algorithm |...
Time Complexity of Merge Sort : • Time Complexity of Mer...
Bubble Sort Videos
Bubble Sort working Example | Brute Force |: • Bubble Sort working Ex...
Bubble Sort Algorithm | Logic tracing with Example: • Bubble Sort Algorithm ...
Selection Sort
Selection Sort | Algorithm Example & Analysis: • Selection Sort Example...
CSEGuru Videos
#CSEGuru Compiler Design Videos:
• Compiler Design
CSEGuru DAA Videos
• Design & Analysis of A...
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