- 356 名前：デフォルトの名無しさん mailto:sage [2008/04/13(日) 22:37:03 ]
- ちょっと考えてる問題があるので意見を聞かせてください。
例えば300個の積み木があるとして、これらは様々な重さ・大きさがあり、5種の色のいずれかが
ついてたとします。
これらを山に積み上げて行くときに、なるべく重さのピークが高い山がたくさん欲しいけれど、以下
の条件を満たさないといけないとします。
１．大きいものほど下にある
２．一山は積み木は10個が限度だけど、赤い積み木が三つ含まれていたら8個が限度になる。
３．一山には2色しか存在してはいけないし、異なる色の境界は1箇所だけ(赤青赤はだめで、赤赤青は良いみたいな)
ものすごく簡略化してしまいましたが、ナップザック問題に条件が加わったようなものになるのかと
思います。
細々とした条件・・・特に色の条件のせいで欲張り法が使えない気がするのですが、こういったものを常識的
時間で解く方法を調べたいので、キーワード程度でも教えてもらえませんか？厳密、近似は問いません。
