35-1 Bin packing

Suppose that we are given a set of \(n\) objects, where the size \(s_i\) of the \(i\)th object satisfies \(0 < s_i < 1\). We wish to pack all the objects into the minimum number of unit-size bins. Each bin can hold any subset of the objects whose total size does not exceed \(1\).

a. Prove that the problem of determining the minimum number of bins required is \(\text{NP-hard}\). (\(\textit{Hint:}\) Reduce from the subset-sum problem.)

The first-fit heuristic takes each object in turn and places it into the first bin that can accommodate it. Let \(S = \sum_{i = 1}^n s_i\).

b. Argue that the optimal number of bins required is at least \(\lceil S \rceil\).

c. Argue that the first-fit heuristic leaves at most one bin less than half full.

d. Prove that the number of bins used by the first-fit heuristic is never more than \(\lceil 2S \rceil\).

e. Prove an approximation ratio of \(2\) for the first-fit heuristic.

f. Give an efficient implementation of the first-fit heuristic, and analyze its running time.

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用