| |
- 238 名前：（ ´∀｀）さん ：04/04/11 22:18 ID:eoFl1OKI
- 1/5
／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
| 最初に問題です。私はアメリカのスーパーで、
| 冷凍コロッケを売りさばこうとしました。
| 冷凍コロッケは以下の 5種類、しかしスーパーに
| 持っていけるのは 8kg まで。それでは、一番売上を
| 上げるには、どのコロッケを売るべきでしょうか。
＼＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
━━━∨━━━━━━━━━━━━━━━━━━━
A. B. C. D. E.
重量 1kｇ 2kｇ 4kｇ 5kｇ 6kｇ
売値 13$ 24$ 50$ 55$ 67$
,_＿
B■∧ /
━ (,,ﾟДﾟ) / ━━━━━ ∧∧━━━━ ∧∧━━━━━
| つ ∇ (ﾟДﾟ,,) (ﾟДﾟ,,)
| ｜┌─┐ /⊂ ヽ /⊂ ヽ
〜| ｜｜□｜ √￣ (_＿_ﾉ〜 √￣ (_＿_ﾉ〜
∪∪ ｜ | || ━┳┛ || ━┳┛
￣￣￣￣｜ | ＝＝＝＝∧＝＝＝＝＝＝＝＝＝＝
／￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣
｜ アメリカで芋コロッケなんて売れるのかよおい。
＼＿＿_ ＿＿＿＿＿＿＿＿＿＿∧＿＿＿＿＿＿＿
／
｜ （売値÷重量）の高い順に選んでけばいいんじゃ？
＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
- 239 名前：（ ´∀｀）さん ：04/04/11 22:18 ID:eoFl1OKI
- 2/5
／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
| 後ろギコ君、問題はそんなに簡単ではありません。
| 売値/kg の高い順に選ぶと、A+B+Cになりますね。
| しかし、実はA+B+Dの組み合わせがベストなのです。
＼＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
━━━∨━━━━━━━━━━━━━━━━━━━
A. B. C. D. E.
重量 1kｇ 2kｇ 4kｇ 5kｇ 6kｇ
売値 13$ 24$ 50$ 55$ 67$
売値/kg 13$ 12$ 12.5$ 11$ 11.16$
A+B+C → 87$(7kg) A+B+D → 92$(8kg)
,_＿ ちなみに B+E → 91$(8kg)
B■∧ /
━ (,,ﾟДﾟ) / ━━━━━ ∧∧━━━━ ∧∧━━━━━
| つ ∇ (ﾟДﾟ,,) (ﾟДﾟ,,)
| ｜┌─┐ /⊂ ヽ /⊂ ヽ
〜| ｜｜□｜ √￣ (_＿_ﾉ〜 √￣ (_＿_ﾉ〜
∪∪ ｜ | || ━┳┛ || ━┳┛
￣￣￣￣｜ | ＝＝＝＝∧＝＝＝＝＝＝＝＝＝＝
／￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣
｜ へぇ。kgあたりの売値が一番安いDも選ばれるのか。
＼＿＿_ ＿＿＿＿＿＿＿＿＿＿∧＿＿＿＿＿＿＿
／
｜ Cのコロッケは引っかけだったんだな…。
＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
- 240 名前：（ ´∀｀）さん ：04/04/11 22:19 ID:eoFl1OKI
- 3/5
／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
| この問題は一般に「ナップサック問題」と呼ばれます。
| 限られた容量のナップサックに品物を詰め、合計金額を
| できるだけ高くする、みたいな問題というわけです。
|
| で、上の例ですが、もし重量の制限が上がるかわりに
| コロッケの種類も増えたとしたらどうでしょう？
＼＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
━━━∨━━━━━━━━━━━━━━━━━━━
重量制限 1t
A. B. C. D. E. … Z. AA AB. …
重量 1kｇ 2kｇ 4kｇ 5kｇ 6kｇ … 3kｇ 8kｇ 7kｇ …
売値 13$ 24$ 50$ 55$ 67$ … 35$ 90$ 82$ …
,_＿
B■∧ /
━ (,,ﾟДﾟ) / ━━━━━ ∧∧━━━━ ∧∧━━━━━
| つ ∇ (ﾟДﾟ,,) (ﾟДﾟ,,)
| ｜┌─┐ /⊂ ヽ /⊂ ヽ
〜| ｜｜□｜ √￣ (_＿_ﾉ〜 √￣ (_＿_ﾉ〜
∪∪ ｜ | || ━┳┛ || ━┳┛
￣￣￣￣｜ | ＝＝＝＝∧＝＝＝＝＝＝＝＝＝＝
／￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣
｜ 総当たりで計算…としたら悪夢だ…ｹｲｻﾝｽﾙﾀﾞｹﾃﾞ ﾑﾈﾔｹｼｿｳ｡
＼＿＿_ ＿＿＿＿＿＿＿＿＿＿∧＿＿＿＿＿＿＿
／
｜ やっぱり、何かパッと解ける方法があるんですよね？
＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
- 241 名前：（ ´∀｀）さん ：04/04/11 22:20 ID:eoFl1OKI
- 4/5
／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
| 残念ながら、パッと解ける方法は今のところありません。
| 前ギコ君の言うとおり、組み合わせを総当たり、が基本です。
| ｼｶｼ ｱｸﾑ ﾄﾊ ｷｷｽﾞﾃﾅﾘﾏｾﾝﾈ｡ ｺﾛｯｹ ﾊﾟﾗﾀﾞｲｽﾃﾞﾊ ﾅｲﾃﾞｽｶ｡
＼＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
━━━∨━━━━━━━━━━━━━━━━━━━
ナップサック問題は、現状ではコンピュータでも
解くのに指数オーダーの時間がかかってしまう。
例えば品物100個なら1分で解けても、200個なら1時間、
400個なら150日、1000個なら約190億年といった感じ。
,_＿
B■∧ /
━ (,,ﾟДﾟ) / ━━━━━ ∧∧━━━━ ∧∧━━━━━
| つ ∇ (ﾟДﾟ,,) (ﾟДﾟ,,)
| ｜┌─┐ /⊂ ヽ /⊂ ヽ
〜| ｜｜□｜ √￣ (_＿_ﾉ〜 √￣ (_＿_ﾉ〜
∪∪ ｜ | || ━┳┛ || ━┳┛
￣￣￣￣｜ | ＝＝＝＝∧＝＝＝＝＝＝＝＝＝＝
／￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣
｜ ひゃ、190億年…いきなり単位が大きくなりすぎだろ。
＼＿＿_ ＿＿＿＿＿＿＿＿＿＿∧＿＿＿＿＿＿＿
／
｜ まさに指数関数的だな、こりゃ。
＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
- 242 名前：（ ´∀｀）さん ：04/04/11 22:21 ID:eoFl1OKI
- 5/5
／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
| この調子で答えを探していては氏んでも答えが出ないので、
| 「パーフェクトな正解でなくてもそれに近い答え」を探すのが
| 一般的です。が、その方法に関しては…反響があれば。
＼＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
━━━∨━━━━━━━━━━━━━━━━━━━
,_＿ 今回はレポート課題はありません。
B■∧ /
━ (,,ﾟДﾟ) / ━━━━━ ∧∧━━━━ ∧∧━━━━━
| つ ∇ (ﾟДﾟ,,) (ﾟДﾟ,,)
| ｜┌─┐ /⊂ ヽ /⊂ ヽ
〜| ｜｜□｜ √￣ (_＿_ﾉ〜 √￣ (_＿_ﾉ〜
∪∪ ｜ | || ━┳┛ || ━┳┛
￣￣￣￣｜ | ＝＝＝＝∧＝＝＝＝＝＝＝＝＝＝
／￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣
｜ レポートなしは有り難いな。
＼＿＿_ ＿＿＿＿＿＿＿＿＿＿∧＿＿＿＿＿＿＿
／
｜ きっと全然オチが思いつかないんだろう。
＼＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
|
|
