サブロウ丸

主にプログラミングと数学

【Python】ビンパッキング問題

離散数学の組合せ論の代表的な問題としてビンパッキング問題というのがあります。
十分に用意された品物を、複数個のビン(容器)に詰めるときの最大利益を求める問題です。
このときビンの個数が1つであればナップサック問題と呼ばれる問題になります。

このビンパッキング問題を応用して以下のような問題を作ってみました。

f:id:inarizuuuushi:20170918112120p:plain:w600


整数計画法による解法を載せます。
f:id:inarizuuuushi:20170918112157p:plain:w600

おなじみ
Pythonpulpを使って実装すると
ソースコード


実行結果

入力
うさぎ0が食べるりんごの量は1.2
うさぎ1が食べるりんごの量は2.2
うさぎ2が食べるりんごの量は1.0
うさぎ3が食べるりんごの量は0.7
うさぎ4が食べるりんごの量は1.8
うさぎ5が食べるりんごの量は2.3
うさぎ6が食べるりんごの量は1.4
うさぎ7が食べるりんごの量は1.8
うさぎ8が食べるりんごの量は0.7

出力
ゲージ0に入れるうさぎは 7
ゲージ0に必要なりんごの個数は1.8 -> 0.0
ゲージ1に入れるうさぎは 
ゲージ1に必要なりんごの個数は0.0 -> 0.0
ゲージ2に入れるうさぎは 2
ゲージ2に必要なりんごの個数は1.0 -> 1.0
ゲージ3に入れるうさぎは 8
ゲージ3に必要なりんごの個数は0.7 -> 0.0
ゲージ4に入れるうさぎは 0 3
ゲージ4に必要なりんごの個数は1.9 -> 2.0
ゲージ5に入れるうさぎは 1 4
ゲージ5に必要なりんごの個数は4.0 -> 4.0
ゲージ6に入れるうさぎは 5 6
ゲージ6に必要なりんごの個数は3.7 -> 4.0