問題タブ [partition-problem]

これは難しいアルゴリズムの問​​題です：

リストを2つの部分（合計）に分割し、それらの合計が（最も）互いに最も近いものにします

リストの長さは1<=n <= 100であり、それらの（数）の重みは1 <= w<=250です。

例：23 65134 32 95123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2.list = 4 5 6

アルゴリズムはありますが、すべての入力で機能するわけではありません。

1. 初期化。リストlist1=[]、list2 = []
2. 要素の並べ替え（指定されたリスト）[23 32 34 65 95123134]
3. 最後の1つをポップ（最大1つ）
4. 違いの少ないリストに挿入

実装：list1 = []、list2 = []

1. 134挿入リスト1を選択します。list1 = [134]
2. 123挿入リスト2を選択します。list1に挿入すると、差が大きくなるためです
   。3. 95を選択し、list2を挿入します。sum（list2）+ 95-sum（list1）が小さいためです。

等々...

ここに別の動的プログラミングの質問があります（Vazirani ch6）

次の 3-PARTITION 問題を考えてみましょう。整数 a1...an が与えられたとき、{1...n} を次のように 3 つの互いに素な部分集合 I、J、K に分割できるかどうかを判断したいと考えています。

合計(I) = 合計(J) = 合計(K) = 1/3*合計(すべて)

たとえば、入力 (1; 2; 3; 4; 4; 5; 8) の場合、パーティション (1; 8)、(4; 5)、(2; 3; 4) があるため、答えは「はい」です。一方、入力 (2; 2; 3; 5) の場合、答えはノーです。n と (Sum a_i) の時間多項式で実行される 3-PARTITION の動的計画法のアルゴリズムを考案して解析します。

どうすればこの問題を解決できますか? 2パーティションは知っていますが、まだ解決できません

Given a set A containing n positive integers, how can I find the smallest integer >= 0 that can be obtained using all the elements in the set. Each element can be can be either added or subtracted to the total. Few examples to make this clear.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1 (-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

ねえ、私は正の数の配列をk個の部分に分割して、各部分が（ほぼ）同じ合計になるようにするアルゴリズムを見つけるための助けを探しています...

1,2,3,4,5,6,7,8,9 en k = 3アルゴリズムは、この1,2,3,4,5 | 6,7|8,9の順序で分割する必要があります。要素を変更することはできません...欲張りアルゴリズムを見つけるのは簡単ですが、常に最適なソリューションを返すバックトラックバージョンを探しています...

誰もが何かヒントを得ましたか？

私はアンドロイド用の数学アプリを作っています。これらのフィールドの 1 つで、ユーザーは int (数字なし、0 より大きい) を入力できます。アイデアは、この int を構成するすべての可能な合計を double なしで取得することです (この場合は 4+1 == 1+4)。知られている唯一のことは、この 1 つの int です。

例えば：

ユーザーが 4 を入力すると、アプリに次のように返してもらいたいとします。

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

明らかに 4 == 4 なので、それも追加する必要があります。これを行う方法について何か提案はありますか?

マトリックスをほぼ偶数の行で分割したいと思います。たとえば、これらの寸法 155 x 1000 のマトリックスがある場合、新しい各マトリックスのおおよその寸法が 15 X 1000 である場合、それを 10 で分割するにはどうすればよいですか?

私はJavaをまったく使い始めたばかりです。私はAndroidゲームを書いていますが、指定された数になる可能性のあるすべての合計（2を含むまたは8より大きい数を含む組み合わせを除く）を含むint配列の配列を生成する必要があります。

例： ganeratePatterns(5)配列を返す必要があります

私はすでにそこのようにこれをやろうとしています。与えられた数になる可能性のあるすべての合計を取得しますが、このhttp://introcs.cs.princeton.edu/java/23recursion/Partition.java のようにするのは非常に困難です。 html

解決

100％正しくは動作せず、非常にきれいですが、私のゲームには十分です

ここからSumIteratorクラスを使用しました。SumIterator.class古いバージョンではすべての組み合わせが返されないため（10の場合は[5,5]など）、このコードfor(int j = n-1; j > n/2; j--) {をこれ に変更する必要があります。for(int j = n-1; j >= n/2; j--) {

そして、toIntArray関数を使用しました。StackOverflowでうさぎを設立しましたが、リンクを忘れたので、ここにソースがあります：

ヘテロジニアスコンピューティングのスケジューラーを実行しています。

タスクは、期限とデータレートによって識別でき、2次元グラフと見なすことができます。画像を参照してください：

長方形は、GPUでスケジュールされるタスクと、CPUでスケジュールされる外部タスクを識別します。

問題は、最適な長方形を作成するためのパラメータを効率的に特定したいということです。つまり、ほとんどのタスクを含む長方形です。現在の長方形にドットを追加できるかどうかを判断する関数が存在すると見なすことができます。

最大20.000（ドット）のタスクがあり、軸は任意の長さにすることができます

この問題を解決する既知のアルゴリズム/データ構造はありますか？

過去にこれと同様の問題に遭遇しましたが、この問題を解決する方法がまだよくわかりません。問題は次のようになります。

サイズ n <= 1000 および k <= n の正の整数配列が与えられます。これは、配列を分割する必要がある連続したサブ配列の数です。最小 m を出力する必要があります。ここで、m = max{s[1],..., s[k]} であり、s[i] は i 番目の部分配列の合計です。配列内のすべての整数は 1 ～ 100 です。例:

配列を 2+1 に分割 | 1+2 | 3 は m を最小化します。

私の強引なアイデアは、最初のサブアレイを位置 i で終了させ (可能なすべての i に対して)、可能な限り最良の方法で残りのアレイを k-1 サブアレイに分割しようとすることでした。ただし、これは指数関数的なソリューションであり、決して機能しません。

だから私はそれを解決するための良いアイデアを探しています。もしお持ちでしたら教えてください。

ご協力いただきありがとうございます。