2

コードを書いているときに、次の問題を見つけました。簡単に説明します。

Aの値の合計とBの値の合計の差が最小になるように、配列AとBの float Xの配列を分割します。

これは私が行っていた調査の一部でしたが、この操作を効率的に実行する方法が見つかりません。

編集：

これが体育、SPOJ、または宿題のような数学のコンテストからのものであると信じている人に答えるために、そうではありません. 私は、因数aとb のセットで既に因数分解された数pを b=a+1 となるように分割しようとしたときに、これについて好奇心を持っていました。両側からログを取得すると、この問題が合計の差を最小化することと同等であることを示すことができますが、それが私が行き詰まったところです。

4

1 に答える 1

3

最初の簡単なアイデアです。動的計画法を使用します。
この問題はナップザック問題に変換できると思います。X合計を最大化するには ( array が存在する)から項目を選択する必要がありますが、値Aを超えないようにしてください(sumX - sumA)( array からの項目の合計が存在しますB)。動的プログラミング アプローチによってナップザックの問題を解決するアルゴリズムについては、wikiを参照してください。たとえば
、この解決策は間違っている可能性があります。

于 2013-06-29T00:26:36.480 に答える