7

問題は次のとおりです。

正の整数の集合 { a1 , a2 , a3 , ... , an } が与えられ、その中に同じ数が存在しない (a1 は一度しか存在しない、a2 は一度しか存在しない、...) 例: A = {12 , 5 、7、91}。問題: A の 2 つの素集合 A1 = { b1,b2,...,bm } と A2 = { c1,c2,...,ck} があり、b1+b2+...+bm = c1+ c2+...+ck ?

次の点に注意してください: A1 と A2 が A をカバーすることは必須ではないため、問題が自動的に部分和問題に還元されることはありません。例: A = {2,5,3,4,8,12} A1= {2,5} したがって、A1 の合計は 7 A2= {3,4} したがって、A2 の合計は 7記述されたプロパティなので、問題は解決されます。

どうすればこの問題を解決できますか? 可能なすべての (互いに素な) サブセットを見つけて、それらの合計を計算し、2 つの等しい合計を見つけるよりも良いことはできますか?

お時間をいただきありがとうございます。

4

4 に答える 4

3

問題ありません。ここにO(1)解決策があります。

A1 = {}; 
A2 = {};
sum(A1) == sum(A2) /* == 0 */

QED。

真剣に、実行できる最適化の 1 つは (正の数について話していると仮定して) 以下のサブセットのみをチェックすることsum(A)/2です。

のすべての要素にAは、次の 3 つのオプションがありますO(3^N)。

  1. 中に入れてA1
  2. 中に入れてA2
  3. 捨てる

これは Perl での単純な解決策です (一致をカウントします。存在をテストしたいだけであれば、早期復帰が可能です)。

use List::Util qw/sum/;

my $max = sum(@ARGV)/2;
my $first = shift(@ARGV); # make sure we don't find the empty set (all joking aside) and that we don't cover same solution twice (since elements are unique)
my $found = find($first,0, @ARGV);
print "Number of matches: $found\n";

sub find {
    my ($a, $b, @tail) = @_;
    my $ret = $a == $b? 1 : 0; # are a and b equal sub-sets?
    return $ret unless @tail;

    my $x = shift @tail;
    $ret += find($a + $x, $b, @tail) if $a + $x <= $max; # put x in a
    $ret += find($a, $b + $x, @tail) if $b + $x <= $max; # put x in b
    return $ret + find($a, $b, @tail); # discard x
}
于 2009-02-08T12:49:46.713 に答える
2

答えが「いいえ」の場合、n個の数すべての合計は少なくとも2^n-1です。したがって、たとえばnが大きく、数値が32ビット整数の場合、答えはほとんどの場合「はい」です。nが小さい場合は、おそらくブルートフォース攻撃が可能です。

最も難しいケースは、おそらくnが約30の場合です。

于 2009-02-08T13:11:28.153 に答える
1

部分和問題と同じように解けると思います。a0,a1,...,ai のサブセットが s になり、ai を含む場合に真となるブール関数 Q(i,s) を取ります。動的計画法を使用して、すべての i と s について計算できます (これは標準的なアプローチです)。次に、関連付けられた行に複数の真の値を持つ s の Q のすべての値をスキャンできます。

そのような が存在する場合、合計が同じである 2 つの異なるサブセットが見つかったことを意味します。それらはばらばらではないかもしれませんが、各セットから共通の要素を削除して、合計が等しい 2 つのばらばらのセットを取得できます。ただし、そのうちの 1 つが空である可能性があります。

于 2009-02-08T20:49:05.570 に答える
0

この問題は、少なくともSUBSET-SUMと同じくらい難しいようです。Aの2つのサブセットが見つかった場合：B = {b1、...、bp}とC = {c1、...、cq}で、b1 + ... + bp = -c1 ....- cq、または、存在しないと判断した場合は、SUBSET-SUM（A）を解きました（0∈Aの自明なケースを無視します）。

BとCがAをカバーする義務がないということはどういう意味かわかりません。そのため、問題が自動的に部分和問題に還元されることはありません。SUBSET-SUMの定義を確認してください。

于 2009-02-10T05:09:23.910 に答える