As in classical bin packing problem, this is an algorithm that optimises the number of bins of a certain size used to hold a list of objects of varying size.
In my variant I also work with a second constraint that is the bins must hold a certain minimum size in them. For example :
max_pm = 10, min_pm = 5 ; If we input
[8,2,3] then the packing
[[8, 2], ] is not valid. Some problems also don't hold any solution in which case we should return
I implemented this simply as a post-processing solution validation, is there any more optimised way to do it ? I need an optimised solution if it exists, heuristics are not good which is why I've choosed a recursive branching approach.
Items here are size 4 tuples, last value is weight.
from copy import deepcopy def bin_pack(items, min_pm, max_pm, current_packing=None, solution=None): if current_packing is None: current_packing =  if not items: # Stop conditions: we have no item to fit in packages if solution is None or len(current_packing) < solution: # If our solution doesn't respect min_pm, it's not returned, return best known solution instead for pack in current_packing: if sum((item for item in pack)) < min_pm: return solution # Solutions must be cleanly copied because we pop and append in current_packing return deepcopy(current_packing) return solution # We iterate by poping items and inserting in a list of list of items item = items.pop() # Try to fit in current packages for pack in current_packing: if sum((item for item in pack)) + item <= max_pm: pack.append(item) solution = bin_pack(items, min_pm, max_pm, current_packing, solution) pack.remove(item) # Try to make a new package if solution is None or len(solution) > len(current_packing): current_packing.append([item]) solution = bin_pack(items, min_pm, max_pm, current_packing, solution) current_packing.remove([item]) items.insert(-1, item) return solution
print bin_pack([(0,0,0,1), (0,0,0,5), (0,0,0,2), (0,0,0,6)], 3, 6) # displays [[(0, 0, 0, 6)], [(0, 0, 0, 2), (0, 0, 0, 1)], [(0, 0, 0, 5)]] print bin_pack([(0,0,0,1), (0,0,0,5), (0,0,0,2), (0,0,0,6)], 4, 6) # displays None