Bin Packing Problem 편집하기

'''Bin Packing Problem''' is a combinatorial optimization problem that involves packing objects of varying sizes into a finite number of bins with a fixed capacity while minimizing the number of bins used.
==Definition==
Given:
*A set of '''n''' items, each with a weight '''w<sub>i</sub>'''.
*A set of bins, each with a fixed capacity '''C'''.
The objective is to pack all items into the smallest number of bins such that:
*The total weight of items in any bin does not exceed its capacity.
*Each item is placed in exactly one bin.
==Variants==
There are multiple variations of the bin packing problem:
*'''Online vs. Offline Bin Packing'''
**In the '''offline version''', all items are known in advance.
**In the '''online version''', items arrive sequentially and must be placed immediately.
*'''One-Dimensional vs. Multi-Dimensional'''
**In '''1D bin packing''', items have only one attribute (e.g., weight).
**In '''2D or 3D bin packing''', items also have height, width, or volume constraints.
*'''Bin Packing with Conflicts'''
**Some items cannot be placed in the same bin due to constraints.
==Example==
Suppose we have 5 items with weights: '''[4, 8, 1, 4, 7]''' and bin capacity '''10'''. The optimal packing might be:
{| class="wikitable"
!Bin!!Items
|-
|Bin 1||[8, 1]
|-
|Bin 2||[7]
|-
|Bin 3||[4, 4]
|}Total bins used: '''3'''
==Heuristic Algorithms==
Since the bin packing problem is NP-hard, exact solutions are computationally expensive for large inputs. Common heuristic approaches include:
*'''First-Fit (FF)'''
**Place each item in the first available bin that has enough space.
*'''Best-Fit (BF)'''
**Place each item in the bin that will have the least remaining space after insertion.
*'''Worst-Fit (WF)'''
**Place each item in the bin with the most remaining space.
*'''Next-Fit (NF)'''
**Similar to First-Fit but keeps using the current bin until it is full.
==Implementation==
A simple '''First-Fit algorithm''' in Python:<syntaxhighlight lang="python">
def first_fit(weights, bin_capacity):
    bins = []
    for w in weights:
        placed = False
        for b in bins:
            if sum(b) + w <= bin_capacity:
                b.append(w)
                placed = True
                break
        if not placed:
            bins.append([w])
    return bins

items = [4, 8, 1, 4, 7]
capacity = 10
bins = first_fit(items, capacity)
print("Bins used:", bins)
</syntaxhighlight>
==Applications==
*'''Cloud Computing'''
**Allocating virtual machines to servers efficiently.
*'''Logistics'''
**Packing cargo in containers with minimal waste.
*'''Memory Management'''
**Allocating memory blocks in operating systems.
==See Also==
*[[Knapsack Problem]]
*[[Bin Covering Problem]]
*[[Packing Problem]]
*[[Combinatorial Optimization]]
*[[Approximation Algorithm]]
[[Category:Algorithm]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*