Chapter 1 Algorithms : Packing Flashcards
What is packing problem
This is where you are given boxes of different size and task is how to best pack thede into a number of equal volume bins
How to calauclte the LOWER BOUND for number of bins needed
What does lower bound show
= add the weigths or heights whatever of ALL THE BOXES
2) divide by the volume of one bin
3) ROUND UP
Lower bound tells you the MINIMUM number of bins needed to store all the boxes ASSUMING they can all perfectly fit into the boxes with no gaps. In reality This Never happens
Why need to roundup when finding lower bound ?
This is because can’t have like 0.5 of a bin , not possible
What are the three techniques used for bin lacking
First fit algorithm
First dit decreasing algorithm
Full bin METHOD
How to do First fit algorithm
Imagine conveyor belt comes , whatever comes first no matter what you just put it in the first bin .
2) keep doing this until you csn’t, open a new bin
3j every time you check , start form bin 1 and go down
How to represent this bin packing notation
Left open bins, right have the capacities
Write down what goes in what bin and what ORDER, and as they arrive, adjust the capacity by crossing out to show
Finally if saturated make sure to say it
How to record wasted space?
Just count all the empty space in the boxes once everything has been accounted for
How to do FIRST FIT DECREASING ALGORITHM,
1) order in descending order
2) now do it like normal first fit, whatever comes try fit until end
How to do FULL BIN METHOD
Although inspection, what technique can we use to try do it
Use INSPECTION to try and find the most combinations of saturated bins
1) pick biggest box and try make saturated
2) if can’t, chose next biggest box and try again
3) keep trying like this snd eventually you should get a good solution
Why is FULL BIN METHOD NOT AN ALGORITHM?
What condition does it violate
this is because INSPECTION and element of CHOICE is involved
= therefore AMBIGUOUS, foes against 3 conditions
What are advantage and disavdnatged to full bin packing
+ is that csn find good / optimal solution
- can be crazy hard with long sets of numbers and decimals too
WHAT IS A HEURISTIC ALGORITHM?
Why are first fit and first fit decreasing heuristic
Can it give you the optimal solution tho?
Heuristic algorithm is an algorithm that is generally efficient but does not guarantee the OPTIMAL SOLUTION , but csn give it just not guaranteed
First fit and decreasing give good solutions but not necessarily optimal = heuristic
2) IT CAN GIVE OPTIMAL but not guaranteed
How to derrive the complexity for first fit and first fit decreasing
Start recognise they are the same algorithm when ordered for first fit decreasing
Complexity depends on the number of COMPARISONS MADE
In this scenario assume Esch time we need ti open a new box (worse case)
- first we check if it can go into first box = 1 comparison
- then for the second we check first then second
- etc thus the total comparisons are 1+2+3+4 … n
If we transform this series to a sequence you get 1, 3, 6 10 = triangle numbers
Nth term of thid is 1/2n (n+1)
Altenraitvly that is the sum of 1 to n of the sequence n =1/2n (n+1)
BOTH CASES THIS IS QUADRATIC COMPLEXITY
Complexity for first fit snd decreasing
Quadratic
What does it mean when can all be fitted basically
Just check for lowe bound snd if they add up
