私の教科書にこの問題があります： それぞれが異なる値V（i）を持つn個のアイテムのグループを与えられた場合、アイテムを3つのグループに分けて最高の値を持つグループが最小化されます。この最大のグループの価値を与える。アイテムのグループを3つの別々のグループに分割するためのアルゴリズムとは何ですか？
私はこの問題の2つのパイルバリアントを実行する方法を知っています：問題のバックナップをナップザックアルゴリズムで実行する必要があります。しかし、私はこの問題を解決する方法としてかなり困惑しています。誰も私に何か指針を与えることができますか？
回答：0-1ナップサックなどほとんど同じこと、2D
もののタフ宿題の問題。これは基本的に3パーティション問題の最適化バージョンです。
http://en.wikipedia.org/wiki/3-partition_problem
（あなたが述べたように、ナップサックと）それはビンパッキング、パーティション、およびサブセット和と密接に関連しています。しかし、それは起こり易く、それはそれがそのいとこよりも難しくなるNP完全です。とにかく、関連する問題の動的プログラミングソリューションを見てみることをお勧めします（私はパーティションから始めますが、DPソリューションの非ウィキペディアの説明を見つけてください）。
更新：お詫び申し上げます。私はあなたを誤解した。 3パーティションの問題は、入力を3つのセットではなく3つのセットに分割します。私が言ったことの残りの部分はまだ適用されますが、あなたの変種が強力にnp完全ではないという新たな希望があります。
私は問題にいくつかの情報を追加しました。 –
@RichieLi正直な質問：問題を台無しにしないように詳細をどれくらいしたいですか？すなわち、所望の反復関係があまりにも大きい（私はそれを持っていない、自分自身でそれを働かせなければならないだろうか）？ – ccoakley
ええ、私はそれを自分で解決しようとします。それは夕方の予定だから、もし私がもっと助けが必要なら、私はあなたに戻ってきます。 –
「The Best」については数学的には分かりませんが、最初に各グループに1つのアイテムを含むグループの集団を構築することが1つの方法です。次に、必要な数の最終グループよりも多くのグループがある場合は、最も低い値の2つのグループを抽出し、それらを結合して新しいグループにして、コレクションに戻します。これは、ハフマン圧縮ツリーの構築方法と似ています。
例：
1 3 7 9 10
becomes
4(1+3) 7 9 10
becomes
9 10 11(1+3+7)
私たちはこれについてまだ学んでいないので、私はこの問題にこれを使うべきではないと私は思っています。 –
ピッキングニット：欲張りのアプローチは、（固定アルファベットの可変長符号化のための）ハフマンの場合に最適です。問題の数字がきれいに分散されている場合にのみ、パーティションに対して合理的に実行されます（「きれいに」という言葉より正確ではありません）。その質問が「ダイナミックプログラミング」とタグ付けされていたことを考えると、私は割り当ての目的が欲張りなテクニックを使用していないと推測しました。 – ccoakley
で、F [i]は[J] [k]は、第2セットの最初のセットと値kに値jを有することが可能であるかどうかを示してみよう最初の商品はです。
f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]]です。
となりました。最初はf[0][0][0] = Trueです。
をf[i][j][k] = Trueとすると、答えはと公式にはと定義されています。
しかし、i番目のアイテムは3番目のセットに入る可能性があるので、f [i] [j] [k] = f [i-1] [jv [i]] [k]またはf [i -1] [j] [kv [i]]またはf [i-1] [j] [k] 'である。 –
また、f [i] [j] [k] = Trueのいくつかのi、j、kの解を考えるとき、s [i] - jを使って3番目の集合の重みを計算しますここで、s [i]は、最初のi個のアイテムの重みの合計です（開始時に線形時間で事前に計算されます）。 –
@j_random_hackerはい、そうです。私のミス – Topro
それが現れて消えたので、ここに欲張りの失敗{100、51、49、40、30、20、10}の例があります。最適な答えは完全な分割であり、貪欲に最小のグループに割り当てられていない最大の要素を適用することはできません。 – ccoakley
私は同じ教科書を持っています。ブライアンディーンは私にそれを与えた;） – joshim5