import random
import math
def first_fit_pack(lst):
"""
Place the packs into bins by the first-fit algorithm.
The algorithm try to place the packs (keeping their order) into
the bins so that the next item is always placed in the first bin
where it fits. If the pack fits in none of the bins, it opens a
new bin. (Every pack is measured by a number between 0 and 1,
let us call the weight of it. Packs fit into a bin, if the sum
of their weights is not more than 1.)
:param lst: List of the packs. The function make a copy of the
list before packing.
:returns: The number of necessary bins.
"""
weights = list(lst)
# TODO Write here the code of FF algorithm!
return -1
def ffd_pack(lst):
"""
Place the packs into bins by the first-fit decreasing algorithm.
The algorithm try to place the packs into the bins like in the
previous algorithm but first sort them decreasing by weights.
:param lst: List of the packs. The function make a copy of the
list before packing.
:returns: The number of necessary bins.
"""
weights = list(lst)
# TODO Write here the code of FFD algorithm!
return -1
def best_fit_pack(lst):
"""
Place the packs into bins by the best-fit algorithm.
The algorithm try to place the packs (keeping their order) into
the bins so that the next item is always placed in the bin
where the omittance is minimal.
:param lst: List of the packs. The function make a copy of the
list before packing.
:returns: The number of necessary bins.
"""
weights = list(lst) # weights = lst would be wrong! why?
bins = []
for weight in weights:
max_fulness = -1.0
max_pos = -1
for i in range(len(bins)):
if (bins[i] + weight <= 1.0) and (bins[i] > max_fulness):
max_pos = i
max_fulness = bins[i]
if max_pos == -1:
bins.append(weight)
else:
bins[max_pos] += weight
return len(bins)
if __name__ == '__main__':
# TODO Generate a random sequence of 1000 numbers between 0 and 1
# instead of the next list
packs = [0.34, 0.34, 0.33, 0.33, 0.33, 0.33]
the_sum = math.ceil(sum(packs))
bf = best_fit_pack(packs)
ff = first_fit_pack(packs)
ffd = ffd_pack(packs)
print("OPT: ", the_sum)
print(" FF: ", ff)
print("FFD: ", ffd)
print(" BF: ", bf)