8

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

リストを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）が小さいためです。

等々...

4

5 に答える 5

7

これをナップサック問題として再定式化することができます。

最大重量M/2を保持できるビンに取り付ける必要がある総重量Mのアイテムのリストがあります。ビンに詰められたアイテムは、可能な限り重量を量る必要がありますが、ビンが保持する量を超えないようにしてください。

すべての重みが負でない場合、この問題はNP完全性が弱く、多項式時間解があります。

この問題の動的計画法ソリューションの説明は、ウィキペディアにあります。

于 2010-12-18T18:56:12.170 に答える
4

問題はNPCですが、それには疑似多項式アルゴリズムがあります。これは2分割問題です。これを解決するには、サブセット和問題の疑似多項式時間アルゴリズムの方法に従うことができます。入力サイズが入力値に多項式的に関連している場合、これは多項式時間で実行できます。

あなたの場合（重み<250）は多項式です（重み<= 250n=>合計<=250n ^ 2であるため）。

Sum =重みの合計とすると、2次元配列Aを作成してから、列ごとにAを作成する必要があります。

A [i、j] = true if（j ==weight[i]またはj--weight[i] = weight [k]（kはリストにあります））。

このアルゴリズムを使用した配列の作成には、O（n ^ 2 * sum / 2）が必要です。

最後に、真の価値を持つ最も価値のある列を見つける必要があります。

次に例を示します。

アイテム：{0,1,2,3}重み：{4,7,2,8}=>合計=21合計/2 = 10

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

したがって、a [10、2] == trueであるため、パーティションは10、11です。

これは私がここで見つけ、問題を解決するために少し編集したアルゴリズムです。

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

T [N / 2]を返す代わりに（最大から最小の順序で）真である最初のT[i]を返しました。

この値を与えるパスを見つけることは難しくありません。

于 2010-12-18T19:27:43.087 に答える
2

この問題は、少なくともNP完全問題のサブセット和と同じくらい難しいものです。あなたのアルゴリズムは欲張りアルゴリズムです。このタイプのアルゴリズムは高速であり、近似解をすばやく生成できますが、NP完全問題の正確な解を見つけることはできません。

ブルートフォースアプローチはおそらく問題を解決するための最も簡単な方法ですが、要素が多すぎると遅くなります。

  • 要素を2つのセットに分割するすべての可能な方法を試して、合計の絶対差を計算します。
  • 絶対差が最小になるパーティションを選択します。

すべてのパーティションの生成は、0〜2 ^ nの各整数のバイナリ表現を検討することで実行できます。ここで、各2桁は、対応する要素が左または右のパーティションにあるかどうかを決定します。

于 2010-12-18T18:54:07.703 に答える
0

同じ問題を解決しようとすると、私は次のアイデアに直面しました。これは解決策が多すぎるように見えますが、直線的な時間で機能します。それが機能しないことを示したり、それが解決策ではない理由を説明したりする例を提供できますか？

arr = [20,10,15,6,1,17,3,9,10,2,19] # a list of numbers

g1 = []
g2 = []

for el in reversed(sorted(arr)):
    if sum(g1) > sum(g2):
        g2.append(el)
    else:
        g1.append(el)

print(f"{sum(g1)}: {g1}")
print(f"{sum(g2)}: {g2}")
于 2021-04-20T18:42:30.787 に答える
0

Typescriptコード：

import * as _ from 'lodash'
function partitionArray(numbers: number[]): {
    arr1: number[]
    arr2: number[]
    difference: number
} {
    let sortedArr: number[] = _.chain(numbers).without(0).sortBy((x) => x).value().reverse()
    let arr1: number[] = []
    let arr2: number[] = []
    let median = _.sum(sortedArr) / 2
    let sum = 0

    _.each(sortedArr, (n) => {
        let ns = sum + n
        if (ns > median) {
            arr1.push(n)
        } else {
            sum += n
            arr2.push(n)
        }
    })
    return {
        arr1: arr1,
        arr2: arr2,
        difference: Math.abs(_.sum(arr1) - _.sum(arr2))
    }
}
于 2021-08-01T16:14:32.847 に答える