0

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)

4

1 に答える 1

2

ブール整数計画法を使用して解決できます。いくつかのアルゴリズム (例: Gomory または分枝限定) と無料のライブラリ (例: LP-Solve) が利用可能です。

リストの合計を計算し、それを s と呼びます。リストの数字を 2 倍にします。2倍になった数字がa、b、cだとします。次に、次の方程式系があります。

Boolean x,y,z 

a*x+b*y+c*z >= s

Minimize ax+by+cz!

ブール変数は、対応する数値を加算するか (true の場合)、減算するか (false の場合) を示します。

[編集]

変換された問題は、「ナップザック問題」とも見なすことができることに注意してください。

Boolean x,y,z 

-a*x-b*y-c*z <= -s

Maximize ax+by+cz!
于 2011-04-21T09:07:36.393 に答える