0

I've modified the bin packing algorithm from here: First Fit Decreasing Algorithm. It now works for my particular application except that I noticed there's nothing to prevent items from being assigned to more than one bin.

In my program, I wish to return a list of lists where the sublists represent individual bins, and the sublist elements are the keys of the items placed in them.

I have tried using items.remove(item) before and after both lines with .append() but that has not prevented the item from being assigned to more than one bin. 

def binpack(articles,bin_cap):
    items = list(articles.items())   
    items.sort(key=lambda i: i[1], reverse=True)
    bins = [[items[0]]]

    for item in items:
        for bin in bins:
        # check to see if item will fit in bin
            if sum(i[1] for i in bin) + item[1] <= bin_cap:
                bin.append(item)
                break
        else:
        # item didn't fit into any bin, start a new bin
            bin = []
            bin.append(item)
            bins.append(bin)

    bin_contents = [[item[0] for item in bin] for bin in bins]
    print(bin_contents)

When tested:

articles = {0:20, 1:13, 2:22}
binpack(articles, bin_cap = 36)

Returns:[[2, 1], [2], [0]]

The item with key 2 is placed in the first and second bin when it should only be placed in one

Desired:[[2,1], [0]]

Jacob Myer
  • 479
  • 5
  • 22
  • 1
    Why do you initialize the bins with 1st item? You can try change the for loop to ‘while items:’ and do ‘item = items.pop(0)’. This gets rid of duplicates. – Tim Feb 18 '19 at 22:54
  • I have the items sorted by highest volume to lowest, so I knew that would be included in the first bin. I had originally placed it there in an effort to solve a different problem and haven’t ran the function without it so it may work if I change that to an empty list – Jacob Myer Feb 18 '19 at 23:06
  • 1
    Give the while statement a try and start with an empty list. It should work – Tim Feb 18 '19 at 23:12
  • actually all it took was the bins = [] , I've fed it several tests and it works excellently – Jacob Myer Feb 19 '19 at 00:43
  • Very old question, but the answer is [here](https://stackoverflow.com/questions/7392143/python-implementations-of-packing-algorithm). – Mehdi May 04 '22 at 20:50

0 Answers0