خوارزمية لإيجاد فرعية ضمن مجموعتين من الأعداد الصحيحة التي مبالغ المباراة

Question

أنا أبحث عن خوارزمية والتي يمكن أن تتخذ مجموعتين من الأعداد الصحيحة (سواء كانت إيجابية أو سلبية) و تجد مجموعات فرعية داخل كل نفس المبلغ.

مشكلة مشابهة فرعية مبلغ المشكلة إلا أن أبحث عن مجموعات فرعية على كلا الجانبين.

هنا مثال:

قائمة {4, 5, 9, 10, 1}

قائمة ب {21, 7, -4, 180}

لذلك المباراة الوحيدة هنا هي:{10, 1, 4, 9} <=> {21, 7, -4}

لا أحد يعرف إذا كان هناك خوارزميات القائمة على هذا النوع من المشاكل ؟

حتى الآن, الحل الوحيد لدي هو نهج القوة الغاشمة التي يحاول كل تركيبة ولكنه ينفذ في الأسي الوقت كنت قد وضعت الحد الثابت على عدد من العناصر التي يجب مراعاتها لتجنب ذلك من أخذ وقتا طويلا.

فقط حل آخر يمكنني التفكير به هو تشغيل مضروب على كل القوائم والبحث عن المساواة هناك ولكن هذا لا يزال غير فعالة جدا و يأخذ أضعافا مضاعفة تعد قوائم الحصول على أكبر.

Answer 1

ماذا قال آخرون هو الصحيح:

1. هذه المشكلة هي NP كاملة.سهلة الحد هو المعتاد فرعية-المبلغ.يمكن أن تظهر هذه بالإشارة إلى أن مجموعة فرعية من مبالغ إلى مجموعة فرعية ب (ليس كل فارغ) إلا إذا كان غير فارغة فرعية من الاتحاد (-ب) المبالغ إلى الصفر.

2. هذه المشكلة ليست فقط ضعيفة NP-complete, في أنه متعدد الحدود في حجم أرقام المشاركة, ولكن هو محدوس أن يكون المتسارع في اللوغاريتمات.وهذا يعني أن المشكلة أسهل من اللقب "NP-complete" قد توحي.

3. يجب عليك استخدام البرمجة الديناميكية.

فما أنا من المساهمة في هذا النقاش ؟ حسنا, رمز (في بيرل):

@a = qw(4 5 9 10 1);
@b = qw(21 7 -4 180);
%a = sums( @a );
%b = sums( @b );
for $m ( keys %a ) {
    next unless exists $b{$m};
    next if $m == 0 and (@{$a{0}} == 0 or @{$b{0}} == 0);
    print "sum(@{$a{$m}}) = sum(@{$b{$m}})\n";
}

sub sums {
    my( @a ) = @_;
    my( $a, %a, %b );
    %a = ( 0 => [] );
    while( @a ) {
        %b = %a;
        $a = shift @a;
        for my $m ( keys %a ) {
            $b{$m+$a} = [@{$a{$m}},$a];
        }
    %a = %b;
    }
    return %a;
}

فإنه يطبع

sum(4 5 9 10) = sum(21 7)
sum(4 9 10 1) = sum(21 7 -4)

لذا لا سيما أن هناك أكثر من حل واحد يعمل في المشكلة الأصلية!

تحرير:المستخدم itzy صحيح وأشار إلى أن هذا الحل كان خطأ ، والأسوأ من ذلك بطرق متعددة!!أنا آسف جدا حول هذا و لقد نأمل أن تعالج هذه المخاوف في الكود أعلاه.ومع ذلك ، لا تزال هناك مشكلة واحدة وهي أن أي مجموعة فرعية-المبلغ, إلا يطبع أحد الحلول الممكنة.على عكس المشاكل السابقة التي كانت مباشرة الأخطاء ، وأود أن تصنف هذه المتعمد القيد.حظا سعيدا و حذار من الأخطاء!

Answer 2

مثل فرعية مبلغ المشكلة هذه المشكلة ضعيف NP-complete, لذلك لديه الحل أن يعمل في وقت متعدد الحدود(م) ، حيث م هو مجموع كل الأرقام التي تظهر في المشكلة سبيل المثال.يمكنك تحقيق ذلك مع البرمجة الديناميكية.كل مجموعة يمكن أن تولد كل ممكن المبالغ عن طريق ملء 2-الأبعاد الثنائية الجدول ، حيث "صحيح" في (ك ، م) يعني أن مجموعة فرعية مبلغ م يمكن أن يتحقق من خلال اختيار بعض العناصر من العناصر k الأولى من المجموعة.

يمكنك ملء تكراري - تعيين (ك ، م) إلى "صحيح" إذا كان (k-1 ، م) إلى "صحيح" (من الواضح إذا كان يمكنك الحصول على م من ك-1 العناصر يمكنك الحصول عليه من العناصر ك قبل لا ترد ك ال) أو إذا (k-1 و m-d) يتم تعيين إلى "true" حيث d هي قيمة ك-ال عنصر في مجموعة (حالة حيث يمكنك اختيار ك-ال عنصر).

ملء الجدول يحصل لك كل مبالغ في العمود الأخير (واحد يمثلون المجموعة الكاملة).هل هذا لكل من مجموعات مشتركة مبالغ.يمكنك التراجع الفعلي فرعية تمثل الحلول من خلال عكس عملية التي يمكنك استخدامها لملء الجداول.

Answer 3

وشكرا جزيلا لجميع الردود سريعة!

والحل البرمجة الديناميكية لا يختلف حقا إلى المقاربة شاملة لدينا في الوقت الحالي وأعتقد إذا كنا بحاجة إلى الحل الأمثل نحن بحاجة للنظر في كل تركيبة ممكنة ولكن الوقت الذي يستغرقه لتوليد هذه قائمة شاملة من مبالغ هي أيضا طويل.. لم اختبار سريع والوقت الذي يستغرقه لتوليد جميع المبالغ الممكنة ل× عدد العناصر يذهب بسرعة كبيرة أكثر من 1 دقيقة:

11 elements took - 0.015625 seconds
12 elements took - 0.015625 seconds
13 elements took - 0.046875 seconds
14 elements took - 0.109375 seconds
15 elements took - 0.171875 seconds
16 elements took - 0.359375 seconds
17 elements took - 0.765625 seconds
18 elements took - 1.609375 seconds
19 elements took - 3.40625 seconds
20 elements took - 7.15625 seconds
21 elements took - 14.96875 seconds
22 elements took - 31.40625 seconds
23 elements took - 65.875 seconds
24 elements took - 135.953125 seconds
25 elements took - 282.015625 seconds
26 elements took - 586.140625 seconds
27 elements took - 1250.421875 seconds
28 elements took - 2552.53125 seconds
29 elements took - 5264.34375 seconds

والذي لمشكلة الأعمال نحاول حل غير مقبول حقا .. أنا ستعمل العودة الى لوحة الرسم ونرى ما إذا كنا بحاجة فعلا لمعرفة كل الحلول أو يمكننا أن مجرد علاقة مع واحد ( أصغر / أكبر فرعية، على سبيل المثال) بدلا من ذلك ونأمل أن يمكن أن تساعد ببساطة المشكلة وجعل بلدي خوارزمية تؤدي إلى expectaion.

والشكر كل نفس!

Answer 4

ومبلغ فرعية هي NP-كاملة ويمكنك polynomially لحد من مشكلة لذلك، حتى مشكلتك هي NP-كاملة أيضا.