問題: BinPacking
[SRM 598 div1 250]
問題の要約:
容量300のビンがあります． 100-300の大きさのアイテムがリストで渡されます.
ビンにアイテムを詰めるために少なくとも何本のビンが必要でしょうか
(問題の原文は下にあります)
引数:
- item : itemのリスト
例:
アイテムのリスト (150,150,150,150,150)
容器数 3つ
実装の方針
- 基本的な方針は300に出来るだけ近いペアを見つけてビンに詰めていく(L29-33) 例外はいくつかある
- <追記>[例外0] 大きさ100と200のアイテムがある場合は 最優先で取り除く (L9-12)
- [例外1] 大きさ100のアイテムが3つ以上ある場合は 先に3個づつ取り除く (L4-17)
- [例外2] 残りが1つの場合 単体でビン詰めして処理を終了させる(L21-23)
[例外3] 残りが2つの場合でも合計値が300をオーバーした場合はそれぞれを単体でビン詰めして処理を終了させる<追記>[例外4] 大きさ300のアイテムがあった場合は事前に取り除く<追記>[例外4] 大きさ201以上のアイテムがあった場合は事前に取り除く←なくてもいいので削除しました- <追記>[例外5] これ以上ペアが作れない場合にはそれぞれを単体でビン詰めして処理を終了させる(L24-26)
(修正しました)
原文:
PROBLEM STATEMENT
Fox Ciel has some items. The weight of the i-th (0-based) item is item[i]. She wants to put all items into bins.
The capacity of each bin is 300. She can put an arbitrary number of items into a single bin, but the total weight of items in a bin must be less than or equal to 300.
You are given the tuple (integer) item. It is known that the weight of each item is between 100 and 300, inclusive. Return the minimal number of bins required to store all items.
DEFINITION
Class:BinPacking
Method:minBins
Parameters:tuple (integer)
Returns:integer
Method signature:def minBins(self, item):
CONSTRAINTS
-item will contain between 1 and 50 elements, inclusive.
-Each element of item will be between 100 and 300, inclusive.
