هل ستفشل هذا الحد من الغطاء الدقيق في مجموع فرعي بسبب إيجابي كاذب محتمل؟

Question

بعد إزالة مجموعات متعددة ومجموعات تحتوي على عناصر غير موجودة في $ S $ .

$ s $ = $ [9،6،7،4،5،1،8] $

$ C $ = $ [[9،6،7]، [4،5]، [1] 8]]] $

تحويل القيم في $ C $ من قيم الفهرس المشترك مع $ S $ . (يجب أن يتم ذلك قبل لمس $ S $ )

$ c $ = $ [[1،2،3]، [4،5]، [6] 7]]] $

وفعل الشيء نفسه بالنسبة ل $ S $

$ s $ = $ [1،2،3،4،5،6،7] $

square كل $ x $ عدد صحيح في كل من $ S $ و $ C $

$ f (x) $ = $ x ^ 2 $ ، $ x ∈ s $ ثم $ C $

$ S $ = $ [1، 4، 9، 16، 25، 36، 49] $

$ C $ = $ [[1،4،9]، [16،25]، [36] 49]] $

ثم قم بإزالة جميع المجموعات باستخدام مبالغ متكررة لمنع الإيجابيات الخاطئة. هذا يعني أنه لا $ [1]، [1] S ... $ التي يمكن استخدامها، لتلخيص مجموع $ S $ ، وهذا يعني أيضا $ [1،4،9] $ أو $ [ 4،9،1] $ . (اترك واحدة رغم ذلك!)

1. بعد التحول مكتمل استخدام Subset-Sum Solver وتحديد المبلغ الإجمالي ك 140 دولارا $ (مجموع مجموع $ S $ )
2. حدد قائمة الأعداد الصحيحة كمجموعة ملخصة من $ C $ = $ [[14]، [41] ، [85]] $
3. تشغيل الخوارزمية والحصول على الحل

السؤال

هل هذا التخفيض من الغطاء الدقيق في مجموع فرعي لكل سفر إيجابي كاذب؟

Answer 1

إذا لم تكن متأكدا حقا ما إذا كان التخفيض سيعمل، فربما لن يفعل ذلك. عند إجراء تخفيض، يجب أن يكون لديك دائما خطة لكيفية إثبات ذلك.

في هذه الحالة، نتطلع لمعرفة ما إذا كان $ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... + n ^ 2 $ يمكن أن يكون مكتوبة كمجموع من المربعات بطريقة أخرى (والتي ستكون إيجابية كاذبة).

لدينا هذا $ 4 ^ 2= 2 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2 $ . هذا يكفي لبناء مثال مضاد.

دع $ s={1،2،3،4،5،5،6،7 \} $ و $ c={\ {1،2 \}، \ {2،3 \}، \ {2،5 \}، \ {2،6 \} \، \ {2،7 \}، \ {1، 3،4،5،6،7 \} \} $ .

لا يوجد غطاء دقيق (الطريقة الوحيدة للحصول على $ 4 $ هي أن تأخذ $ \ {1،3، 4،5،6،7 \} $ ولكن بعد ذلك لا يمكننا أن نأخذ أي مجموعة أخرى لأنها تداخل كل منها).

ومع ذلك، لدينا ذلك:

$$ 1 ^ 2 + 2 ^ 2 + 3 ^ 2 + 4 ^ 2 + 5 ^ 2 + 6 ^ 2 + 7 ^ 2= (1 ^ 2 + 2 ^ 2 ) + (2 ^ 2 + 3 ^ 2) + (2 ^ 2 + 5 ^ 2) + (2 ^ 2 + 6 ^ 2) + (2 ^ 2 + 7 ^ 2) $$

هكذا، يمكننا أن نستنتج التخفيض لا يعمل.