ビンパッキング問題 (Bin Packing Problem)

ビンパッキング問題 (Bin Packing Problem)

ビンパッキング問題 (Bin Packing Problem) は、異なるサイズのアイテムをできるだけ少ないビン（容器）に詰める問題です。

ここでは、具体的な例を示し、Pythonで解く方法を紹介します。

具体例

問題設定:

  • ビンの容量は$ 10 $とします。
  • 詰めるアイテムのサイズは$ [2, 5, 4, 7, 1, 3, 8] $です。

目的:

  • すべてのアイテムを収めるために必要なビンの数を最小化します。

Pythonでの解法

ビンパッキング問題を解くためのアルゴリズムの一つに、First-Fit Decreasing (FFD) 法があります。

この方法では、アイテムを大きい順に並べ替え、各アイテムを順番に最初に収まるビンに詰めていきます。

以下に、FFD法を用いてこの問題を解くPythonコードを示します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def first_fit_decreasing(bin_capacity, items):
    # アイテムを大きい順にソート
    items = sorted(items, reverse=True)
    # ビンのリスト（各ビンの残り容量を保持）
    bins = []
    # 各ビンに詰めたアイテムを記録するリスト
    bin_contents = []
    
    for item in items:
        # アイテムを詰めるためのビンを見つけるフラグ
        placed = False
        
        # 既存のビンにアイテムを詰める
        for i in range(len(bins)):
            if bins[i] >= item:
                bins[i] -= item
                bin_contents[i].append(item)
                placed = True
                break
        
        # 既存のビンにアイテムを詰められなかった場合、新しいビンを追加
        if not placed:
            bins.append(bin_capacity - item)
            bin_contents.append([item])
    
    return bins, bin_contents

# 問題の定義
bin_capacity = 10
items = [2, 5, 4, 7, 1, 3, 8]

# First-Fit Decreasing 法で問題を解く
bins, bin_contents = first_fit_decreasing(bin_capacity, items)

# 結果の表示
print(f"Total bins used: {len(bins)}")
print("Bin contents:", bin_contents)

解説

  1. アイテムのソート:

    • items = sorted(items, reverse=True) でアイテムを大きい順にソートします。

  2. ビンのリスト:

    • 空のビンのリスト bins を作成します。

  3. アイテムの配置:

    • 各アイテムについて、既存のビンに収められるかをチェックします。
    • 既存のビンに収められる場合、そのビンにアイテムを追加します。
    • 既存のビンに収められない場合、新しいビンを追加し、そのビンにアイテムを入れます。

  4. 結果の表示:

    • 最終的に使用されたビンの数と各ビンの内容を表示します。

Pythonでの解法

このコードを実行すると、以下のような結果が得られます。

1
2
Total bins used: 3
Bin contents: [[8, 2], [7, 3], [5, 4, 1]]

この結果は、3つのビンが使用され、それぞれのビンに収められたアイテムの合計サイズが表示されます。

具体的には、以下のようにアイテムが配置されています。

  • ビン1: 8 + 2 = 10
  • ビン2: 7 + 3 = 10
  • ビン3: 5 + 4 + 1 = 10