SungYong Lee  
Log in

1차원 bin packing 알고리즘. 파이썬으로 구현

80분짜리 공CD를 최대한 아끼면서 내가 좋아하는 노래 최대한 많이 담기

데이터분석
SungYong SungYong

Dec. 9, 2022, 4:57 p.m.

제가 10대일 때는 cd플레이어에서 mp3플레이어로 넘어가는 시기였습니다. 하지만 당시 저희 부모님 차에는 라디오, CD 플레이어 밖에 없었습니다. 여행을 갈 때마다 듣고 싶은 곡을 공CD에 구워서 가곤 했죠. 공CD 한 장에는 80분의 음악을 저장할 수 있기 때문에, 공CD를 최소로 소모하면서 최대한 많은 곡을 담아야 비용을 절약할 수 있었습니다. 

이런 문제를 1차원 bin packing 문제라고 합니다. "시간 길이"라는 한가지 제약조건 하에서 최대한 꽉꽉 채워 넣어야 하는 문제죠. 

이 문제를 prodskill.com 이라는 블로그를 운영하시는 분이 잘 정리해 놓은 내용이 있더라고요. (참고: https://prodskill.com/ko/job-scheduling-using-1d-bin-packing-algorithm-2/) prodskill 블로그에서도 파이썬 코드를 공개해 두었는데, bin-packing-problem이라는 라이브러리를 활용하셨습니다. 

저는 이 블로그에서 소개하는 알고리즘을 파이썬으로 직접 구현하고 시각화 하는 과정을 보여드리고자 합니다. 


아래와 같이 내가 좋아하는 음악 45개의 길이가 분 단위로 주어졌다고 합시다. 

songs = [
    26, 57, 18, 8, 45, 16, 22, 29, 5, 11, 8, 27, 54,
    13, 17, 21, 63, 14, 16, 45, 6, 32, 57, 24, 18,
    27, 54, 35, 12, 43, 36, 72, 14, 28, 3, 11,
    46, 27, 42, 59, 26, 41, 15, 41, 68
]


Bin Packing 문제에서는 item들을 최소한의 Bin에 넣는 문제입니다. 여기에서는 공CD가 Bin이 되고, 한 곡(song)이 item이 되겠죠. 

그래서 CD 역할을 해줄 Bin이라는 클래스를 아래처럼 구현했습니다. 

class Bin:
    def __init__(self, init_space=80) -> None:
        self.items = list()
        self.init_space = init_space
        self.space = init_space

    def add_item(self, item):
        if item <= self.space:
            self.items.append(item)
            self.space -= item
        else:
            raise Exception(f'Song {item} is bigger than space ({self.space})')

    def __str__(self) -> str:
        ss = list()
        for song in self.items:
            ss.append(str(song))
        return f'{round(self.space / self.init_space * 100, 2)}\t' + ', '.join(ss)


기본적으로 __init__에서는 item들을 담을 items 리스트를 초기화해줍니다. 우리 문제에서는 song(곡의 길이)이 item이 됩니다. space는 남은 공간을 저장하기 위한 변수입니다. 인스턴스를 생성할 때 특별한 값을 지정하지 않으면 디폴트로 80으로 지정되도록 설정했습니다. 

add_item 함수는 말 그대로 Bin에 item을 추가하는 역할입니다. 이 문제에서는 공CD에 노래를 하나 추가하는 역할입니다. 남은 space보다 더 큰 item을 담을 수 없으므로, 즉, 공CD 남은 길이보다 더 긴 곡을 담을 수 없으므로, 그런 경우에는 에러를 발생시킵니다. 그렇지 않다면 items에 item을 추가해주고, 그 item의 크기만큼 남은 space에서 빼줍니다. 

__str__ 함수는 프린트를 하기 위한 함수입니다. init_space 대비 얼만큼의 space가 남았는지를 출력하고, 담겨있는 item들의 크기를 string으로 만들어 반환합니다. 


1. Next Fit 알고리즘

가장 무식한 알고리즘입니다. 그냥 순서대로 한 곡씩 CD에 담다가, 다음 곡이 너무 길어서 지금 쓰고 있는 CD에 담을 수 없으면, 다음 CD에 넣기 시작합니다. 

cds = list()
cds.append(Bin())

for song in songs:
    if cds[-1].space <= song:
        cds.append(Bin())
    cds[-1].add_item(song)

print('필요한 CD 갯수: ', len(cds))
print('공간 효율', 1 - sum(songs) / (80 * len(cds)))

for cd in cds:
    print(cd)

위 설명 그대로 파이썬으로 구현한 결과입니다. 

일단 cds라는 리스트를 만들어 공CD를 하나 append합니다. 

그리고 songs를 for문으로 돌립니다.
현재 곡 길이가 마지막 CD의 남은 공간에 들어갈 수 있을지 확인합니다. 가능하지 않다면, 새로운 CD를 꺼냅니다. 여기서는 Bin 인스턴스를 하나 새로 만들어 cds 리스트에 append하는 방식이죠. 
그렇게 하면 어쨌든 마지막 CD에는 현재 곡이 들어갈 충분한 공간이 남아있겠죠. 

결과를 출력해보면 아래와 같습니다. 23장의 CD가 필요하다고 합니다. 23장의 CD 중에 26.5%는 그냥 빈 공간으로 낭비되었습니다. 첫번째 CD는 빈 공간이 무려 67.5%입니다. 

필요한 CD 갯수: 23 공간 효율 0.26521739130434785 67.5 26 6.25 57, 18 13.75 8, 45, 16 6.25 22, 29, 5, 11, 8 66.25 27 16.25 54, 13 52.5 17, 21 3.75 63, 14 16.25 16, 45, 6 60.0 32 28.75 57 13.75 24, 18, 27 32.5 54 41.25 35, 12 1.25 43, 36 10.0 72 30.0 14, 28, 3, 11 8.75 46, 27 47.5 42 26.25 59 16.25 26, 41 30.0 15, 41 15.0 68

그래프로 보면 얼마나 낭비되었는지 보기 어려우니 seaborn을 이용하여 차트를 그리는 함수를 만들겠습니다. 이 코드는 stackoverflow에 올라온 답변을 응용하여 작성했습니다. (https://stackoverflow.com/questions/41296313/stacked-bar-chart-with-centered-labels)

import seaborn as sns
sns.set(rc={'figure.figsize':(11.7,8.27)})

def display_pack_sns(bins):
    bar_cnt = 0

    for bin in bins:
        if len(bin.items) > bar_cnt:
            bar_cnt = len(bin.items)
   
    bars = list()

    for i in range(bar_cnt):
        bars.append(list())
        for bin in bins:
            item = 0 if i > len(bin.items) -1 else bin.items[i]
            bars[i].append(item)

    df = pd.DataFrame(data=reversed(bars)).T
   
    df['cat'] = df.index
    df['cat'] = df['cat'].astype(str)
   
    df = df.melt(id_vars='cat')
   
    ax = sns.histplot(data=df, x='cat', hue='variable', weights='value', discrete=True, multiple='stack', legend=False, palette='hls')

    for c in ax.containers:
        # Optional: if the segment is small or 0, customize the labels
        labels = [int(v.get_height()) if v.get_height() > 0 else '' for v in c]
       
        # remove the labels parameter if it's not needed for customized labels
        ax.bar_label(c, labels=labels, label_type='center')

이제 그래프를 그려봅시다. 

display_pack_sns(cds)



보다시피, 빈 공간이 많이 남은 비효율적인 배치가 되었습니다. 


2. First Fit 알고리즘

조금 더 발전된 방식입니다. 마지막 CD에 곡을 넣을 수 없다고, 무조건 새로운 CD를 추가하지 않고, 첫 CD부터 마지막 CD까지 빈 공간이 있는지 확인하여 가능한 첫 CD에 넣는 방법입니다. 

cds = list()
cds.append(Bin())

for song in songs:
    is_added = False

    for cd in cds:
        if cd.space >= song:
            cd.add_item(song)
            is_added = True
            break
    if not is_added:
        cds.append(Bin())
        cds[-1].add_item(song)

print('필요한 CD 갯수: ', len(cds))
print('공간 효율', 1 - sum(songs) / (80 * len(cds)))


for cd in cds:
    print(cd)

display_pack_sns(cds)


23장이 필요했던 Next Fit 알고리즘과 달리 효율적으로 19장에 다 담았습니다. 

필요한 CD 갯수: 19 공간 효율 0.1105263157894737 1.25 26, 18, 8, 16, 5, 6 1.25 57, 22 3.75 45, 29, 3 5.0 11, 8, 27, 13, 17 6.25 54, 21 3.75 63, 14 1.25 16, 45, 18 1.25 32, 24, 12, 11 11.25 57, 14 3.75 27, 35, 15 0.0 54, 26 1.25 43, 36 10.0 72 7.5 28, 46 13.75 27, 42 26.25 59 48.75 41 48.75 41 15.0 68


3. Worst Fit 알고리즘

각 item(우리 문제에서는 song의 길이)에 대해 bin(우리 문제에서는 공CD) 중에서 가장 남은 크기가 큰 bin에 채우는 방식입니다. 넣을 곳이 없다면 새로운 bin을 만들어 그 안에 넣습니다. 

cds = list()
cds.append(Bin())

for song in songs:
    biggest_space_idx = 0

    for i in range(len(cds)):
        if cds[biggest_space_idx].space < cds[i].space:
            biggest_space_idx = i

    if cds[biggest_space_idx].space < song:
        cds.append(Bin())
        biggest_space_idx = -1
    cds[biggest_space_idx].add_item(song)


   
print('필요한 CD 갯수: ', len(cds))
print('공간 효율', 1 - sum(songs) / (80 * len(cds)))

for cd in cds:
    print( cd)
   

display_pack_sns(cds)

First Fit에 비해 오히려 더 많은 CD가 필요한 결과가 나왔습니다. 

필요한 CD 갯수: 21 공간 효율 0.1952380952380952 7.5 26, 18, 8, 22 7.5 57, 17 23.75 45, 16 0.0 29, 5, 11, 8, 27 16.25 54, 13 13.75 21, 14, 16, 18 21.25 63 2.5 45, 6, 27 30.0 32, 24 28.75 57 32.5 54 23.75 35, 12, 14 1.25 43, 36 10.0 72 13.75 28, 3, 11, 27 42.5 46 15.0 42, 26 26.25 59 30.0 41, 15 48.75 41 15.0 68


4. Best Fit 알고리즘

bin 중에서 가장 남은 space가 작으면서, item보다는 큰 bin에 추가합니다. 적합한 bin이 없으면 새로운bin을 만들어 추가합니다. 

cds = list()
cds.append(Bin())

for song in songs:
    smallest_space = None
    for i in range(len(cds)):
        if song <= cds[i].space:
            if smallest_space == None or cds[i].space < cds[smallest_space].space:
                smallest_space = i

    if smallest_space is None:
        cds.append(Bin())
        smallest_space = -1

    cds[smallest_space].add_item(song)


   
print('필요한 CD 갯수: ', len(cds))
print('공간 효율', 1 - sum(songs) / (80 * len(cds)))

for cd in cds:
    print( cd)
   

display_pack_sns(cds)

First Fit과 마찬가지로19장의 CD에 모두 담을 수 있었습니다.  

필요한 CD 갯수: 19 공간 효율 0.1105263157894737 1.25 26, 8, 45 0.0 57, 18, 5 2.5 16, 22, 29, 11 1.25 8, 27, 17, 21, 6 1.25 54, 13, 12 0.0 63, 14, 3 1.25 16, 45, 18 30.0 32, 24 15.0 57, 11 5.0 27, 35, 14 0.0 54, 26 1.25 43, 36 10.0 72 7.5 28, 46 13.75 27, 42 7.5 59, 15 48.75 41 48.75 41 15.0 68


이 조건에서는 Best Fit 방식과 First Fit 방식이 19장으로 동일한 결과를 도출했지만, 문제 조건에 따라 결과는 Best Fit이 더 나은 쪽으로 달라질 수 있습니다. 다양한 조건을 테스트해볼 필요가 있겠네요. 



내림차순으로 정리한 뒤 적용하기

큰 item을 먼저 배치하면 더 효율적인 결과를 얻을 수 있습니다. 아래처럼 songs를 내림차순으로 정렬합니다. 

songs = sorted(songs, reverse=True)
print(songs)

[72, 68, 63, 59, 57, 57, 54, 54, 46, 45, 45, 43, 42, 41, 41, 36, 35, 32, 29, 28, 27, 27, 27, 26, 26, 24, 22, 21, 18, 18, 17, 16, 16, 15, 14, 14, 13, 12, 11, 11, 8, 8, 6, 5, 3]


1. Next Fit


2. First Fit


3. Worst Fit


4. Best Fit

18장 필요



Leave a Comment:
Log in and leave a comment