- 362 名前：デフォルトの名無しさん mailto:sage [2008/04/14(月) 00:10:42 ]
- 解きたい問題は実は特になくて、この手の雑学の本を読みながら考えていたら、これは欲張り法で
できるのかな？と思ったのです。
で、もうちょっと整理してみました。
ナップサックが10個、取れる品物は300個あるとしてこれらはランダムに5色のいずれかの色がついている
１．品物の価値が高いものを先に詰めねばならない
２．品物の色は、一袋には2色までしか混載できない
３．さらに一袋を詰め終わる過程で、色の切り替わる回数は一回のみ
４．ナップサック一つには10個まで入るが、赤い色の品物を3個入れていたら8個までになる
以上の満たして10個のナップサックをつくり、10袋の価値和を最大にする
２、３は、「赤赤赤赤青青青青青青」はいいが、「赤赤赤赤青青青青赤赤」だめ
４は「赤赤緑緑緑緑緑緑緑緑」で一袋、「赤赤赤緑緑緑緑緑」で一袋になるという感じ
これですっきりしたよーに思いますがどうでしょう？
色がついているのと、4みたいな条件のせいで、欲張れないんじゃないかと思うのです。
