| ナップサック問題 |
|
|
|
|
|
| • | 貨物船で以下の在庫を輸出し利益を得たい |
|||
| • | 貨物船の最大積載重量：100t |
|||
| • | 在庫管理の都合上，輸出する製品は在庫すべてを積む |
|||
| 製品名 |
| 小麦 |
| 米 |
| 大豆 |
| コーン |
| 澱粉 |
| 在庫量 (t) |
| 30 |
| 45 |
| 35 |
| 10 |
| 50 |
| 25 |
| 15 |
| 30 |
| 10 |
| 20 |
| 利益見込 |
|
|
|
| 在庫すべてを輸出 |
||
| した場合 |
||
| Q. 総利益を最大にするには，何を積む？ |
|
|
|
| 製品数がｎ個の時，どんな解法で解く？ |
||
| その解法の最悪計算量は？ |
||