Fractional knapsack Problem Using Greedy Approach | Explained Step by Step
29.1 هزار بار بازدید -
8 سال پیش
-
In this video, we will
In this video, we will discuss about Fractional Knapsack Problem and how to solve Fractional Knapsack Problem using Greedy Approach.
Topics covered in the video-
1) What is a knapsack Problem ?
2) Variants of knapsack Problem-
A) 0/1 Knapsack Problem
B) Fractional Knapsack Problem
3) How to solve Fractional knapsack Problem using Greedy Approach ?
4) Illustration / Numerical Problem illustrating the actual procedure
What is a Knapsack Problem?
You are given a knapsack with a limited weight capacity and some items each of which have a weight and a value.
The problem is- "Which items to place in the knapsack such that the weight limit is not exceeded and the total value of the items is as large as possible.
Variants of Knapsack Problem:
There are two variants of Knapsack Problem :-
1) 0/1 Knapsack Problem
2) Fractional Knapsack Problem
1) 0/1 Knapsack Problem-
In 0/1 knapsack Problem, items are considered indivisible i.e. you cannot break an item, you either take an item or not.
It is solved with a dynamic programming approach.
2) Fractional Knapsack Problem-
In Fractional Knapsack Problem, items are considered divisible i.e. you can take any fraction of an item.
It is solved with a greedy approach.
For details, please watch the video.
Get these handwritten notes from website here-
https://www.gatevidyalay.com/fraction...
Knapsack Problem is an important topic for semester examination as well as competitive examinations like GATE, NET etc.
Watch the complete Algorithms Tutorials here-
How to get the Notes? An Important Up...
Follow us on-
LearnVidFun Facebook : Facebook: learnvidfun
Gate Vidyalay Facebook : Facebook: GateVidyalay
Gate Vidyalay Website : https://www.gatevidyalay.com
For any doubts/ queries, please comment below...
Please...Like, share and comment if you really gained something from this video and don't forget to subscribe yourself for getting the latest updates!
Your support really encourages us to do better....Thank you!! :)
All the best...Keep learning :)
Topics covered in the video-
1) What is a knapsack Problem ?
2) Variants of knapsack Problem-
A) 0/1 Knapsack Problem
B) Fractional Knapsack Problem
3) How to solve Fractional knapsack Problem using Greedy Approach ?
4) Illustration / Numerical Problem illustrating the actual procedure
What is a Knapsack Problem?
You are given a knapsack with a limited weight capacity and some items each of which have a weight and a value.
The problem is- "Which items to place in the knapsack such that the weight limit is not exceeded and the total value of the items is as large as possible.
Variants of Knapsack Problem:
There are two variants of Knapsack Problem :-
1) 0/1 Knapsack Problem
2) Fractional Knapsack Problem
1) 0/1 Knapsack Problem-
In 0/1 knapsack Problem, items are considered indivisible i.e. you cannot break an item, you either take an item or not.
It is solved with a dynamic programming approach.
2) Fractional Knapsack Problem-
In Fractional Knapsack Problem, items are considered divisible i.e. you can take any fraction of an item.
It is solved with a greedy approach.
For details, please watch the video.
Get these handwritten notes from website here-
https://www.gatevidyalay.com/fraction...
Knapsack Problem is an important topic for semester examination as well as competitive examinations like GATE, NET etc.
Watch the complete Algorithms Tutorials here-
How to get the Notes? An Important Up...
Follow us on-
LearnVidFun Facebook : Facebook: learnvidfun
Gate Vidyalay Facebook : Facebook: GateVidyalay
Gate Vidyalay Website : https://www.gatevidyalay.com
For any doubts/ queries, please comment below...
Please...Like, share and comment if you really gained something from this video and don't forget to subscribe yourself for getting the latest updates!
Your support really encourages us to do better....Thank you!! :)
All the best...Keep learning :)
8 سال پیش
در تاریخ 1395/12/09 منتشر شده
است.
29,128
بـار بازدید شده