1. No category

Title
bin-packingの亜種ふたつにかんする備忘録
Author(s)
Citation
小樽商科大学人文研究 (2014), 127: 91-102
Issue Date
URL
飯田, 浩志
2014-03-17
http://hdl.handle.net/10252/5296
Rights
This document is downloaded at: 2015-01-31T19:48:16Z
Barrel - Otaru University of Commerce Academic Collections
91
b
i
r
トp
a
c
k
i
n
gの亜種ふたつにかんする備忘録
飯田浩志*
この小品は， b
i
n
p
a
c
k
i
n
g問題の亜種(拡張もしくは変形)と
in-packingと b
i
n
なるふたつの問題，先行制約っき b
s
t
r
e
t
c
h
i
n
gにかんする覚書になる.
キーワード:組合せ最適化， b
i
n
p
a
c
k
i
n
g問題
本稿は， b
i
n
予a
c
k
i
n
g(ビン詰め)問題の亜種となるふたつの問題i先行制
約っき b
i
n
p
a
c
k
i
n
gとb
i
n
s
t
r
e
t
c
h
i
n
gにかんするメモ書きである.
初版が出てのち改訂されることのない専門書が多い中， 2
0
1
2年初頭に
Korteと Vygenの手になる成書 [
8
Jは，第 5版が刊行された.その中の第四
i
n
p
a
c
k
i
n
g問題は，各 ωJε(O，l
J なる実数列 ω
1，
章で取り上げられてゐる b
すペ
Wz，
…
，
ωnが与へられ (
w
e
i
g
h
tの ω)，それらを容量 1のビン (
b
i
n
)に凡て詰
めるにあたり，使用するビンの本数を最小にする詰め方を求めるといふ，有
名な巡回セールスマン問題と同じく強 NP困難な組合せ最適化問題である.
e
m
)jをビン b(
j
)に a
s
s
i
g
nする函数を b:{
1
，2
，
… ，n
}→
式で書くと，項(it
{
1
，2
，
… ，k
}として，勝手なビン i(
1三
三
t三二 k
)について 2
Jj: b(j)=i叫三二 1なる制
(・)を求めるのが b
i
n予 a
c
k
i
n
gである.最小なったビ
約下で hを最小にする b
ン数 hを最適値と呼ぶ.
i
np
a
c
k
i
n
gに対してはさまざまな近似算法 *1が提案されてゐる.近
この b
悶
似算法とは，一般に最適な詰め方ではないがゆゑに最適値より大きい数(近
*E
m
a
i
l
:h
i
r
o
g
g
i
i
d
a
@
m
e
.
c
o
m
*
1 本稿では，アルゴリズムの意味で算法といふ語を用ゐる.
92
人文研究第 1
2
7輯
似値)を返してしまふけれど，最適値を求めるよりも格段に早く終る手法を
指す.
i
n
p
a
c
k
i
n
gのやうな最小化問題，
ことに少し言葉の定義をしておき度い. b
l
.e
.何ごとか
(
b
i
n
p
a
c
k
i
n
gなら使用するビンの本数)を最小にすることを日
ぉ
的とする問題への近似算法 A に於いて，どんな問題例(in
s
t
a
n
c
e
) 1につい
ほど己
ても， A(
J)と OPT(
J)が Iに A を施して得られる値と最適値(>0とする)
J)ζ kOPT(
J
)が成り立っとき ， k
(云 1
)を A の絶
をそれぞれ表すとして A(
対性能比と呼ぶことにする (
A
(J)注 OPT(J)に注意すると，絶対性能比 1は
，
近似値ではなく最適値を返す算法を暗に示してゐる).またこれに，定数
C
を
加えた A(
J
)skOPT(J)+cが成立するとき ，kを A の漸近的 性能比と呼ぶ
J
J)や
ことにする.以降では，あいまいさを生じるおそれがないのであれば A(
OPT(J)の Iを略すことがある.例へば前述したやうに，最小化問題への近似
二 OPTと書
算法 A は常に最適値以上の値を返すわけだけれども，これを A三
くことカ宝ある.
b
i
n
p
a
c
k
i
n
gへの代表的な近似算法である FFと FFDに就いて，簡単に説
明しておく. FF(
F
i
r
s
t
F
i
t
)は
， ω1から ωnの順に，最初のビンから次次に
見ていって最初に(fi
r
s
t
) 詰められる (
f
i
tする)ビンに詰め，入るピンが無
ければ新たなビンを用意して詰める，といふ算法である (ω1は必ず最初のビ
ンに這入る). FFD (
F
i
r
s
t
F
i
tD
e
c
r
e
a
s
i
n
g
)は
， ωJを大きい順に整列 ω1と
二
μz二三…ミ Wn してから
FFを実行する.たとへば問題例 {
0
.
5，0
.
4，0
.
3，0
.
3，
0
.
3，0
.
2
}では OPT=2，最初のビンに 0
.
5と 0
.
4が入ってしまって FFD=
3になる.じつは乙の例は， FFDの絶対性能比が1.5より良く(小さく)な
らないことを示してゐる.具体的には， FFD三 (
3/2)OPTの等号が成り立つ
i
列になってゐる.かうした伊』を， t
i
g
h
tな{列!といふ *
2
*
2b
i
n
p
a
c
k
i
n
gで P宇 NPの下，いかな近似算法を以てしでも絶対性能比1.5未満
は無理 [
8，p
.4
7
2
J
. この，あらゆる近似算法を考慮した上での絶対性能比の下限
(
in
f
i
m
u
m
)1
.5を指して， b
i
n
p
a
c
k
i
n
gの a
p
p
r
o
x
i
m
a
t
i
o
nr
a
t
i
oは1.5と云ふ [
8，
p
.
4
3
3
J
.
b
i
n
p
a
c
k
i
n
gの亜種ふたつにかんする備忘録
93
2
0
0
7年に Dosa[
3
Jは
， 1
9
9
0年から暫く動かなかった， FFDの漸近的性能
比を表す式 FFDζ(11/9)OPT十 l中の定数項 1が，じつは 6
/
9で t
i
g
h
tにな
i
g
h
tな例は， {
1/2+ε，1/4十 E
，1
/4-2E}X4+{
1/
4十 2
E
，
ることを示した. t
1/4十 2
E
，
1/4-2E
，
1/4-2E
}X2で あ る . ζ れ が OPT=6，FFD=8(ニ
(11/9)OPT十 6
/
9
)を与へる.ここに E>Oは，非常に小さい実数を表す.
0
1
0年に Xiaと Tan[
1
1
Jは
， S
i
m
c
h
i
L
e
v
i[
1
0
J による FFの絶対
他方 2
/
4を 1
2
/
7に改良した [
8，p
.4
7
5
]
. この 1
2
/
7の証明には，漸近的性
性能比 7
能比を表す式 FF三
二 '
17/10)OPT十 7
/
1
0が使われてゐる *3 こちらも， Xiaと
Tan[
1
1
J が導いた結果である(だから，文献口 1
J のタイトルが bounds，
/
1
0は
， 1
9
7
6年の 9
/
1
0以来じつに 3
4年ぶ
と複数形になってゐる).定数項 7
りの改良とのこと [
1
1，p
.1
6
6
9
]
. ただし t
i
g
h
tとは示されておらず， FFDの
/
3で終結した一方， FFのそれ 7
/
1
0は
漸近的性能比を表す式中の定数項は 2
未決である.さらに FFにかんしては，絶対性能比についての議論も終つてな
iaとT
a
n
[
1
1
Jの推測どおり1.7
であると証明されるか，はたまた OPT=
い.X
7
，FFニ 1
2を与へる問題例が見つかるか.云ふまでもなく1.7と 1
2
/
7の聞で
決着する，といふ可能性もある.
i
n
p
a
c
k
i
n
gそれ自体への研究も然る事ながら b
i
n
p
a
c
k
i
n
g
以上のやうな b
の亜種(拡張あるいは変形)となる問題も提案されてゐる.たとへば，各ビ
n
l
i
n
e(後述)で各ビン
ンに就いてーヶだけならビンをはみ出しでも可とか， o
e
s
e
l
l
iと
の中が大きい順になるやうに詰める問題などがある(それぞれ， C
R
i
g
h
i
n
i[
l
J，Dosa他 [
4
J等を参照され度い).以下ニ節では，最近たまたま
i
n
p
a
c
k
i
n
gと b
i
n
s
t
r
e
t
c
h
i
n
gそれぞれにかんする文
目にした先行制約っき b
献についてのメモ書きを残しておくことにする.
iとC
h
e
n[
9，p
.3
0
0
J でも触れられてゐるやうに， FFの漸近的性能比
判例へば L
は1.7より良くならないことが知られてゐる.
94
人文研究第 1
2
7 輯
先行制約っき b
i
n
p
a
c
k
i
n
gに提案された下界に就いて
D
e
l
l
'
A
m
i
c
o他 [
2
Jは，先行制約っき b
i
n
p
a
c
k
i
n
gを e
x
a
c
tに解く手法を提
案するうえで，最適値の下界(見積もり)をいくつか考案してゐる.なかで
もらと
L
4に就いては，最悪の場合の性能比がそれぞれ 1
/
3，1
/
2であること
を示してゐる.本節では其れら下界ふたつに就いて少し書きとめておき度い.
まづ，本節で扱ふのは使用するビン数の最小化問題であって，必要最低限
のビン数を示す最適値より大きくない値が下界であり，その見積もりを表し
てゐる (0-1ナップサック問題のやうな最大化問題なら上界にあたる).精度
の良い下界は，分枝限定法を適用するにあたって展開するノード数を減らす
ために重要な役割を果たす.ただ，下界の精度が良いに越したことはないけ
れど，一般に下界を得るまでにかかる時間と精度とのあいだには t
r
a
d
e
o
f
fの
関係がある.拙稿 [
5
Jで示したやうに，精度が多少悪い見積もりであっても，
それが素早く求まるのであれば，全体として見れば実用になることもある.
b
i
np
a
c
k
i
n
gは，いずれも非負重量判 ω1，ωぃ.，仇をもっ
】
η ヶの項を容量
C のどン(通常は C ニ 1
) に凡て詰めるにあたり，使ふビンの本数を最小に
i
n
p
a
c
k
i
n
gは，特定のふたつの項
する問題であった.さらに先行制約のある b
を詰めるにあたって，先行する方 (
p
r
e
d
e
c
e
s
s
o
r
)を s
t
r
i
c
tに番号の小さいビ
ンに詰めなければならない(同じビンでは不可).先行制約は，項を節点とす
る，サイクルをもたない有向グラフで表すことができる.図 1に例を示す.
0-1ナップサック問題に先行制約があると，例へば図 lなら，項 jを詰める
にあたって項 t
がナップサックに入っていなくてはならない;つまり，項 t
抜きで項 jを詰めることはできない [
7， 1
3
.
2節J
.bin-packingでの図 lは
，
先述のとおり項 iを詰めるビンの番号が項 jを詰めるビンのそれよりも確か
*
4重量 Oの項は，先行制約がある場合には意味を持たせることができる.例へば，
ふたつの項がそれぞれ格納されるビンの聞に少なくともひとつビンを挟みたい
(隣にはしたくない)といふ向きには，先行制約を表すグラフに於いて当該二項
を結ぶ校の中間に重量 0のダミー項を設けるとよい.
b
i
n
p
a
c
k
i
n
gの亜種ふたつにかんする備忘録
95
の
一
一
一
図 1 項 iは項 Jに先行するという制約
ie
.b
(
i
)<b(
j
)を要請する.
に小さくあること， .
D
e
l
l
'
A
m
i
c
o他 [
2
Jは，先行制約っき b
i
n
p
a
c
k
i
n
gへの最適解を求める手法
を提案した.その手法は分枝限定法に基づくが，その分校限定法を実装する
3と L
4に就いては，最悪の
にあたって幾つかの下界を考案してゐる.こと L
/
3，1
/
2であることを，しかも t
i
g
h
tであることを
場合の性能比がそれぞれ 1
も示してゐる (
t
i
g
h
tであることから，求められたら，L
4それぞれの性能比の
導き方に改善の余地なし).このことについて以下，すこ，しメモっておく.
4
e
l
l
'
Am
i
c
o他 [
2
J に倣い，とある問題のいかなる例 Iについても，
以降 D
その最適{直 OPT(J)と下界 L
(I)(ζOPT(I))について Eζ L(J)/OPT(I)
(三 1
)を最悪の場合の性能比，または単に性能比と呼
が成り立っとき，この E
ぶ、ことにする.たとへば性能比
Eニ
1
/
2の下界なら，最適値の半分より悪い
ε のとき，
(小さい)見積もりは出さない，と云ふこと.これに加へてイ >
>L(I)/OPT(I)を満足する問題例 Iの存在を必ず示せるなら
E
'
Eは t
i
g
h
t
といふ *
5 (もうこれより大きくできないギリ).
ゆる
さて，最適値の見積もりには，元の問題におげる制約条件を緩めた問題を
考える.制約条件を緩和した結果，元の問題よりも実行可能解(制約条件を
凡て満たす解)が増えるから最適値が向上するであらう，といふ理屈である.
一般的な緩和の枠組みとして線形緩和，ラグランジュ緩和，代理緩和等あ
るけれど，先行制約を投げる
み
ζ
とで緩和する，つまり通常の b
i
n
p
a
c
k
i
n
gと看
倣すことで得られる下界が L
l:=r~j 助/cl (
K
o
r
t
eと Vygen[
8，p
.4
7
3
J
)
*
5[
2，p
.1
4
9
3
J では，
だらう.
i
ff
o
ra
n
yc
'<c
，と書いたあるものの，不等号が逆の誤植
96
人文研究第 1
2
7 輯
で*
6 逆に先行制約のみ考慮してビンの容量を忘れる，つまり先行制約を表す
zである.たとへば先行
有効グラフに於いて，最長パスを構成する節点数が L
制約に推移的なものがなく，図 1のやうな二項間の関係で凡てが完結すると
zニ 2である(図 2参照).これら下界ふたつに就いては，最適値(必要最
きL
かかわ
低限のビン数)がいくらでも大きくできる(=n
)にも拘らず常に 1を返す最
3:
=m
aX{Ll，L
z
}とし
悪の例をそれぞれに対して簡単に構成できるけれど，L
/
3が出てゐるのは面白い.
ただけで性能比 1
定理 1が，下界 L
3の性能比は 1
/
3だと主張してゐる.さらに証明の最後に
は，項数 n→ ∞ の と き に L3/0PTが上から 1
/
3に限りなく近づく例題があ
る
証明中で構成される実行可能解 H が使うビン数は最適値以上につき，最
終的に，最適値が 3L
14
) の前に，先
3以下であると云ってゐる.また，式 (
i
n
p
a
c
k
i
n
gにおける最適解ではロード(詰められた項
行制約がない通常の b
の重量の総和)がどンの半分未満(実際には半分以下*
7
)であるやうなビンは
図 2 L2はビンの容量を気にしない
*
6 天井 (
c
e
i
l
i
n
g
) 函数
r1は，小数以下を切り上げる. r
Z
.
3
13
.
ニ
*
7 だから，細かいことなんだけど，半分以下しか入つてないかも知れないビン一本
1
4
) は厳密に不等号で成立し，最終的に 1
/
3<
の中味のことを加味せずとも (
L3/0PTではあるまひか.
b
i
n
p
a
c
k
i
n
gの頂種ふたつにかんする備忘録
97
高高ひとつとある.といふのは，もしそんなビンがふたつあったら，合はせ
てひとつにしてビンを減らせるからである.
4は，先行制約を表すグラフにおける最長ノ Tスを与へる項群 P の元
下界 L
それぞれがひとつずつ収められてゐる
L
2個のビンに就いて，残りの項全体の
集合 Qから，先行制約があって同じビンには入れられない項の組を考慮しつ
つ最初から全部は入らない項を排除しつつ，その一部でも構わないのでその
L2個のビン全体に向かつて重量合計/を流し込み(最大流問題)，結果として
余る ~jEQWj
-
fについては Llと同じ考え方
(
1
1
) をあて撮める，といふも
のである.
4の性能比が 1
/
2であることが示される.証明は定理 1のそれ
定理 2で，L
と同じ初期解 H (ビン数 L
2
)から始まり，各ビン tには最長ノ fスを与える項
群 P の元 ρ(i)がひとつずつ収まってゐる.
i
)を通常の b
i
n
p
a
c
k
i
n
gとして解いたとき(ビン数 1
;
)，
証明の途中，R(
(
i
)がもっともロードの少ないビンに入らない場合
項t
(
B
) について:もし
叫(i)が C/2以下であれば，それが入らない解であるなら，どのビンのロード
(
i
)が R
(
i
)U{
t
(
i
)
}の最軽
も C/2を超えてゐるし ;C/2より大きければ， t
量であることから ，R(
i
)に属する元の重量はどれも C/2を超えてゐること
になる *8 よって，どっちの場合であっても (
C
/
2
)
l
i<~jER (i)叫がしたがう.
最終的に定理 1の証明と同様，ここで構成される実行可能解 H の使うピ
L
4以 下
ン数 ZHが ZH三 2Lを満たすから，最適値が 2
つまり， 1
/
2
:
'
二
L4/0PT*9.
以下では，話を簡単にするために慣例に倣って C=lとする.定理 2の証
/
2が t
i
g
h
tであることを示すために，ム/OPTを上からいくら
明の最後に， 1
ほんとうに些細なことながら [
2，p 1
4
9
6
J では，t
(
i
)が R(
i
)U{
t
(
i
)
}の中で最
小のピン (
b
i
n
) とあるけれど，最小の項(it
e
m
) のミスプリ.
*
9小さいことで恐縮だが，解 H を構成する各ビン iに於いて， C 仰 (i)<ωt(
i
)十
LJjES(i
)ω
Jでなければ S
(
i
)の最適性に反する一-S
(
i
)に加えてはもう何も入ら
ω 州 )+
LJj
e
s(
i)
ω
j
)であり，最終的に 1
/2<
ないはず.したがって f<記乞 1(
L4/0PTではないか.
*8
目
98
人文研究第 1
2
7輯
でも 1
/
2に近づけることのできる例題として，先行制約は皆無で，凡ての項
/
2十 εなる例 (
Eは，十分小さい正の数)が提示してある.そこで
の重量が 1
項数 n は偶数であり，先行制約がないから例えば P={1}として，どのふた
つの項も同じピンには入らないので Qから P に伸びる枝はなく 1=0であ
z=1 と 合 は せ て L
4=1 十 r~jEQωjl
り，L
=r
1十 (
1
/
2十 ε)(n-1)1ェ
r
n/2+1/2+(n-1)叶ニ η/2+1.ゆゑに L = L=n
/
2十 1を得る.思ふに，
4
1
/
2十 1より大きい下界を返す簡便な手はないものだらうか.それ
この例に n
lに替はって L
4を良くするやも知れない.
がL
b
i
n
s
t
r
e
t
c
h
i
n
gにかんするメモ
i
n
s
t
r
e
t
c
h
i
n
gへの Ke
l
1
e
r
e
rと Kotov[
6
Jが提案した算法一一号 i
本節は， b
伸し係数これまでの最小値1.6を塗り替へる 1
1
/
7= 1
.5
7
1
4
2
8を実現する
ーーにかんするメモになる.
用意された容量 1のビン m ヶに凡てを納め得ることがあらかじめ分かつ
n
l
i
n
eで次次にやってくる端からビ
てゐる，それぞれが重さを持つ項の列が o
ン m ヶに詰めてい〈ことを考える.通常，ビンの容量がそのままで o
n
l
i
n
eの
格納は無理だから *10 ビンの容量を
s
(二三 1
)に引き伸すとして，この引き伸す
s
t
r
e
t
c
h
i
n
gf
a
c
t
o
r
) sの最小化を目的とするのが b
i
n
s
t
r
e
t
c
h
i
n
gであ
係数 (
る. m=lならもちろんビンを伸ばす必要はなく s =1
.
Ke
l
1e
r
e
rと Kotov[
6
Jが提案した， b
i
ns
t
r
e
t
c
h
i
n
gへの引伸し係数 1
1
/
7を
n
l
i
n
e算法は，ふたつの段階 (
p
h
a
s
e
)から構成される:段階 1[
6，
実現する o
p
.
3
4
5の図 1
J では，段階 2で使うパッチの列を構成するための準備を行う.
例へば s
e
q
u
e
n
c
e
s
{
0
.
4，0
.
4，0
.
5，0
.
6
}と {
0
.
4，0
.
4，
O
.7
}では，ふたつ日の 0
.
4を
格納すべきビンが異なるが， o
n
l
i
n
e算法は今の項の後にどんな列が続いてくる
か知らない. o
n
l
i
n
e算法は o
f
f
l
i
n
e算法(開始前に全情報が開示される)のよう
に振る舞えるけれども逆は無理.前出の FFは o
n
l
i
n
e算法だけど， FFDはさう
でない [
8，p
.4
7
7J
.
*10
b
i
n
p
a
c
k
i
n
gの亜種ふたつにかんする備忘録
99
具体的に段階 1は 3
eBζ msB(ニ mB十 s
B
)三
二3
eB十 3が成立した時点で終
sB，mB，
f
2B それぞれ空ビン，小ビン，中ビン，大ビンの
了する.ここに eB，
総数を指す.各ビンはその中にある項の総重量別に次のやうに呼び分げられ
る:
その名称は
空ビン
小ビン
中ビン
大ビン
超ビン
中味の総重量
w
(
B
)が
O
0<ω (
B
)玉 4/7
4
/
7<ω (B)ζ11/14
1
1
/
1
4<ω (B):
S
:
:1
ω(B)>1
加へて各項の名称も，その重量がこの区分けに準じたものになる.段階 1終
了時に sB>0のとき，段階 2では基本的には三つの小 ビンと一つ'の空ピン
d
か ら な る パ ッ チ と 呼 ば れ る 四 つ 組 B の列 Bl
，
B2，
…，B
k
'を構成し，小項
(
s
m
a
l
litem，:
:
0
:
;
:4
/
7
) と中項 (mediumitem;(
4
/
7，1
1
/
1
4
J
) を前のノてッチか
ら大項 O
argeitem; (
1
1
/
1
4，1
J
) を後ろのパッチから FFで詰めていく.
どのビンにも入らないとき，今のパッチを閉じて次のパッチを開ける.段階
1の終了条件に関聯して ，Aニ msB-3eBと定義される .A=0なら最後の
:
ニe
B
)はビン四つ;でなければ最後のパッチ k
'ニh十 1は空
ノてッチ k'=k(
1三 A三 3
)
. また，大項は小ビンに入る (ζ1+4/7= 1
1
/
ピンなしでビン数 A(
7;ついでに逆で，小項は大ビンに入る).
段階 1で特徴的な点として，
@小項を集めても中ビンにはならない.小項が (
o
n
1
i
neで)来たとき，
argeitemb
i
n，大ビンか超ビン)に入れる(結果，
大項の入るビン O
大ピンが超ビンになるかも)か，小ビンに入れて小ビンのまま *
1
1か
，
*
1
1t
i
n
y項 (
ζ
2
/
7
)を t
i
n
yビンに入れても小ビンのままだから t
i
n
yビンは高高ひ
とつ(補題 1(
c
)
)
.
100
人文研究第 1
2
7輯
空ビンに詰めて小ビンを作るかの三通りしかない.
@中項が絡むのは，それがビンに一つだけ入って他は無しか，あるいは
1
/
1
4十 1
1
/
1
4ニ 1
1
/
7でギリ)かの二通りだけ
二つ入って超ビン(玉 1
(補題 1の
(
b
) と (e)).つまり中項は，他の種類の項と一緒になるこ
とがない.
@大項を空ビンに入れる前に考慮するのは，最大の重量を持つ小ビンの
み*
'
2で，先に触れたように，中ビンとは絡まない.
が挙げられよう.
補題 lの(f)ではらB ニ
oor f2 B ニ O~
とある.段階 2 における算法の説
明では， C
ase1が sB=0のとき， Case2が 2
f
Bニ 0
，s
B>0のときで，
sBニ 2
f
B=0の場合の指示は特にない. Case1に含まれる特殊な場合ではあ
るけれど，ちょっと気になる.補題 1の(f)の証明で，s
B = 0，2
f
Bj= 1か
j
っ時刻 jで来たのが小項のとき，大ビンにその小項が加へられて超ピンに
H1
なったとすると ，SB
=2
f
BH 1=0は起こり得る.では実際に sB=
f
2B=0
のとき，定理 1の証明で C
ase1
，i
.
e
.sB= 0の場合には eB=Oが示されてゐ
る.したがって，凡てのビンのロード(入ってゐる項の総重量)が 1を超え
'
3ところへ mBζ1(補題 1の(c))を加味すれば， mB二 1し
ることはない *
かない(超ビンが無くてもさうだけれど，そもそも超ピンが無いなら m ニ 1
で，さう云った例は最初から除外してよい).よって，段階 2で、加へられる項
は乙の，唯一ロードが 1未満の中ビンに残らず入ることになる.結局，段階
1の終了時に sB=0のときは，段階 2ではただ FFで残りを詰めるとあるけ
*
'
2なぜ小ビンの中でも最大の重量のなのかは，補題 1の(f)の証明と関係してゐる.
*
1
3項全体は最初に与へられた m ヶのビンに入ることが前提なので，全部のビンの
.
.
.
.
.
r
-，
.
r十 1 k'
ロードが lを超えるのは物理的に不可能.同様に，定理 1の証明で B，
に属するビンのロードが平均して lを超えてゐるのだから，残るひとつのパッチ
Brに属する四つのビンのロード，1.e
.段階 1で入ったのと段階 2で入る予定の項
の総重量が 4以上のはずがない.これは，ビンが三つ以下の r=k十 1のときも
同じ.
川
b
i
n
p
a
c
k
i
n
gの亜種ふたつにかんする備忘録
101
れど，sB QB=0であれば FFを持ち出すまでもないやうだ.
こ
段 階 1終了時 eB=sB=Oで全部が中ビン以上である Case1につけ加へ
て
， (もともと全部の項が mヶのビンに入る前提なんだから)この場合には
1
/
2を超える中項や大項が j
u
s
tmヶ(結局，中項は一個以下)で，段階 2で
ζ4/7)である.まだ算法が未終了の時点で
やってくる残りの項はみな小項 (
m ヶのビン全部のロードが二三 1は不可能で，どれかのビンのロードは<1.
/
7=1
1
/
7が
， C
ase1
したがって， FFが乙れから入れるビンについて <1十4
では保証され続ける.
定理 1の証明中最後の段落
rニ k+1(
最後に開いたパッチが列の最後尾
)のとき:ビンが二つ Bh B2の場合で，
でEつ A>0
最初の項とすると， R に段階 1で入った重量と
の総計は 2
-ω (BI)-XI<3/7未満だから，
<3
/
7十1= 1
0
/
7<1
1
/
7なので，
X
Iが
B
Iに入らなかった
X
I以降にやってくる残り重量
XIが 大 項 で あ っ た と し て も
X
Iを含めて以降全部が品に入る，と云ふこ
となのだらう.別の見方をすると，
X
Iを含んで以降の残りを凡て品に詰めた
として， ω(B
)
十ω(
B
2
)<2
だから ω(R)<2 ω(
B
1
)
x
I十XI<3
/
7十1= 1
0
/
7
.
1
さらに r=k+1でビンが三つのとき，最初に B
Iに f
i
tしなかった
に入ったら，
X
Iがまだどのビンにも
X
Iが
品
a
s
s
i
g
nされていないときの s
n
a
p
s
h
o
tに
BI)+ω(品 )+ω(品)十均十(残り )<3とすると， ω(品)十(残り)<
於いて ω(
ω(品 )+ω(品)+(残り)<3一ω(B1)-xI<1
0
/
7
.これから， XIが島に入ったあ
と残り全部が品に入る，
XIが B2 にも
f
i
tしなかったら
*14
w(B1)十y十
ω(品)十 XI十(残り)<3から(残り )<ω(品)+(残り )<3ω (BI)-y-xI<
*
'
4本文中
W
a
s
i
n(b)~
とあるやうに，最後に閉じられるパッチ B， にかんする考察
の (
b
) と同じく ，B
，に最初に入らなかった m が(まだ段階 2では手つかずの)
&に入らないとは，大項は小ビンに入るから，つまり&が(中項 y を含む)中
ビンだったということ(なおかつ m は大項一一中ビンに中項は入るから).存在
すれば唯一の中ビンは，先頭パッチ B，のふたつ日に配置してある(ついでにい
うと，存在すれば唯一の t
i
n
yビンは B，のひとつ呂に配置済)から，これは，パッ
1
'= 1
)でしかもビンは三つ(段階 1の終了時に空ビン無し)と
チがひとっきり (
云ふことになる.段階 1終了時に e
B
(=k
)=0
，msB=A=3はアル.
人文研究第 1
2
7輯
102
1
0
/
7
y
. よって品では y+(
残り)<10/7となって m後の残りが全部入る，
と云ふ解釈でいいのだらう，たぶ、ん.
最後に記述されてゐる ，sの下界 4/3と，そこで示された 1
1
/
7の差がどう
云ふ風に縮まっていくのか，興味深いところである.
参考文献
[
l
J Alb巴r
t
oC
e
s
e
l
l
iandG
i
o
v
a
n
n
iR
i
g
h
i
n
i，Ano
p
t
i
m
i
z
a
t
i
o
na
l
g
o
r
i
t
h
mf
o
rt
h
e
o
r
d
巴r
e
do
p
e
n
e
n
db
i
n
p
a
c
k
i
n
gp
r
o
b
l
e
m
.Q
ρe
rRes5
6
(
2
)4
2
5
3
6(
2
0
0
8
)h
t
t
p
:
/
/
d
x
.
d
o
i
.
o
r
g
/
1
0
.
1
2
8
7/
o
p
r
・
e
.
1
0
7
0
.
0
4
1
5
.
o
s
eC
a
r
l
o
sDiazD
i
a
zandManuelI
o
r
i，Theb
i
np
a
c
k
i
n
g
[
2
J MauroD
e
l
l
'
A
m
i
c
o，J
problemw
i
t
hp
r
e
c
e
d
e
n
c
ec
o
n
s
t
r
a
i
n
t
s
.OperRes6
0
(
6
)1
4
9
1
5
0
4(
2
0
1
2
)h
t
t
p
:
/
/
d
x
.
d
o.
io
r
g
/
1
0
.
1
2
8
7/
o
p
r
e
.
1
1
2
0
.
1
1
0
9
.
[
3
J GyorgyDosa，Thet
i
g
h
tboundo
ff
i
r
s
tf
i
td
e
c
r
e
a
s
i
n
gb
i
n
p
a
c
k
i
n
ga
l
g
o
r
i
t
h
m
i
sFFD(I):
S
:1
1/90PTI 十 6
/
9
.I
n
:B
.Chen，M.P
a
t
e
r
s
o
nandG
.Zhang(
E
d
s
.
)
6
1
4，
p
p
.1
1
1，
S
p
r
i
n
g
e
r2
0
0
7，
h
t
t
p
:
/
/
d
x
.
d
o
i
.
o
r
g
/
1
0
.
1
0
0
7/
ESCAPE2
0
0
7，LNCS4
9
7
8
3
5
4
0
7
4
4
5
0
41
.
[
4
J GyδrgyDosa，Z
s
o
l
tTuza andD
e
s
h
i Ye，Binp
a
c
k
i
n
gw
i
t
h“
L
a
r
g
e
s
tI
n
Bottom"c
o
n
s
t
r
a
i
n
t
:t
i
g
h
t
e
rboundsandg
e
n
e
r
a
l
i
z
a
t
i
o
n
s
.JCombOptim(
2
0
1
1
)
h
t
t
p
:
/
/d
x
.
d
o
i
.
o
r
g
/
1
0
.
1
0
0
7/
s
1
0
8
7
8・0
1
1
9
4
0
8
0
.
ida，
An
o
t
eont
h
emax-min0
1knapsackp
r
o
b
l
e
m
.JCombQ戸t
i
m
[
5
JH
i
r
o
s
h
iI
3
(
1
)8
9
9
4(
1
9
9
9
)h
t
t
p
:
/
/
d
x
.
d
o.
ip
r
g
/
1
0
.
1
0
2
3
/A
:1
0
0
9
8
2
1
3
2
3
2
7
9
.
[
6
J HansK
e
l
l
e
r
e
randV
l
a
d
i
m
i
rKotov，Ane
f
f
i
c
i
e
n
ta
l
g
o
r
i
t
h
mf
o
rb
i
ns
t
r
e
t
c
h
ゆe
rResL
e
t
t4
1
(
4
)3
4
3
6(
2
0
1
3
)h
t
t
p
:
/
/
d
x
.
d
o
i
.
o
r
g
/
1
0
.
1
0
1
6/
j
.o
r.
12
0
1
3
.
0
3
.
ing.O
0
0
5
.
r
i
c
hP
f
e
r
s
c
h
yandDavidP
i
s
i
n
g
e
r，Kn~ρsacl， P
r
o
b
l
e
m
s
.
[
7
J HansK
e
l
l
e
r
e
r，Ul
S
p
r
i
n
g
e
r2
0
0
4
.
[
8
J BernhardKorteandJ
e
n
sVygen，C
o
m
b
i
n
a
t
o
r
i
a
lOptimization-Theoη and
A
l
g
o
r
i
t
h
m
s(
A
l
g
o
r
i
t
h
m
sandC
o
m
b
i
n
a
t
o
r
i
c
s
，Volume2
1
)5
t
hE
d
i
t
i
o
n，S
p
r
i
n
g
e
r
2
0
1
2，h
t
t
p
:
/
/
d
x
.
d
o.
io
r
g
/
1
0
.
1
0
0
7/
9
7
8
36
4
2
2
4
4
8
891
8
.
[
9
J ChungLunL
iandZhi-LongCh巴n，B
i
n
p
a
c
k
i
n
gproblemw
i
t
hconcavec
o
s
t
s
o
fb
i
nu
t
i
l
i
z
a
t
i
o
n
.NavalResL
o
g
i
s
t5
3
(
4
)2
9
8
3
0
8(
2
0
0
6
)h
t
t
p
:
/
/
d
x
.
d
o.
io
r
g
/
1
0
1
0
0
2
/
n
a
v
.
2
0
1
4
2
[
1
0
J DavidS
i
m
c
h
i
L
e
v
i，Neww
o
r
s
t
c
a
s
er
e
s
u
l
t
sf
o
rt
h
eb
i
n
p
a
c
k
i
n
gproblem
NavalResL
o
g
i
s
t4
1
(
4
)5
7
9
8
5(
1
9
9
4
)
[
l
1JBinzhouXiaandZ
h
i
y
iTan，T
i
g
h
t
e
rboundso
ft
h
eF
i
r
s
tF
i
ta
l
g
o
r
i
t
h
mf
o
r
t
h
eb
i
n
p
a
c
k
i
n
gp
r
o
b
l
e
m
.D
i
s
c
r
e
t
eA
p
p
l
i
e
dM
a
t
h
e
m
a
t
i
c
s1
5
8
(
1
5
)1
6
6
8
7
5(
2
0
1
0
)
h
t
t
p
:
/
/
d
x
.
d
o.
io
r
g
/
1
0
.
1
0
1
6
/
i
.
d
a
m
.
2
0
1
0
.
0
5
.
0
2
6
.
ω
目
田
田
目
目