مجموع مستهدف من عناصر تستخدم مرة واحدة: الصف السابق واتجاه التحديث

كل عنصر فرصة اختيار واحدة

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

يعرض CSES في Money Sums مجاميع يمكن صنعها من قائمة قطع، ويوضح مرجع CP-Algorithms نموذج الاختيار صفر أو واحد وأثر الصف السابق واتجاه التحديث. نستعمل الفكرة المعروفة هنا للوصول المنطقي إلى مجموع، لا لتعظيم قيمة تحت سعة. الأرقام والمصفوفات والشواهد التالية مؤلفة للمقال، ولم ننقل مثال المرجع أو كوده أو نقدم حلًا بوصفه تسليمًا في مسابقته.

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

تعريف المجاميع من قائمة، مرجع نموذج 0-1 والصف السابق.

هوية العنصر تختلف من قيمته

نرقم عناصر القائمة من صفر إلى ثلاثة. العنصر صفر قيمته ثلاث، والعنصر واحد سبع، والعنصر اثنان سبع، والعنصر ثلاثة اثنتا عشرة. العنصران واحد واثنان متساويان في القيمة لكنهما مختلفان في الهوية. اختيار كليهما يضيف سبعة مرتين من عنصرين حقيقيين في القائمة، ولا يخالف شرط الاستعمال مرة واحدة لكل هوية.

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

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

ماذا يحمل صف الوصول؟

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

قبل معالجة أي عنصر، يمكن تكوين صفر باختيار المجموعة الفارغة، ولا يمكن تكوين مجموع موجب. نضع نعم عند صفر ولا عند بقية المجاميع. هذه حالة بدء ضرورية؛ ستسمح بإضافة قيمة العنصر الأول إلى صفر. الصفر هنا مجموع، بينما المجموعة الفارغة شاهد له، وليس معنى نعم أن لدينا عنصرًا صفريًا في القائمة.

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

الأخذ والترك من الصف السابق

عند معالجة عنصر قيمته v، نأخذ حالة المجموع s من حالتين في الصف السابق. إما أن s كان ممكنًا دون العنصر الحالي، فنتركه، أو كان المجموع s ناقص v ممكنًا قبل العنصر، فنضيف هذا العنصر مرة لنصل إلى s. إذا تحقق أي الخيارين تصبح الحالة الجديدة نعم. وإذا لم يتحققا تبقى لا.

نحتاج أن يكون s ناقص v داخل مجال المجاميع الذي نعالجه. ولأن القيم موجبة، لا نحتاج الانتقال من مجموع أكبر إلى أصغر في هذا العقد. نقرأ الحالتين من الصف السابق الذي لم يستخدم العنصر الحالي، لا من خانة كتبتها للتو أثناء المرحلة نفسها. هذا هو ما يمنع الانتقال من صفر إلى ثلاثة ثم من الثلاثة الجديدة إلى ستة بعنصر واحد قيمته ثلاث.

ترك العنصر يبقي أي مجموع قديم ممكنًا؛ إضافة عنصر لا تحذف الاختيارات التي استغنت عنه. لذلك تتسع مجموعة الممكن أو تبقى كما هي عند الانتقال إلى صف جديد، ما دمنا نبقي العناصر القديمة والحد نفسه. أما حذف عنصر من الأصل فهو تغيير للبيانات، وليس خطوة إضافة تتبع هذا الاستدلال، ويحتاج إعادة مراجعة النتائج.

من ثلاث إلى أول سبعة

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

نضيف العنصر واحد ذي القيمة سبع. نأخذ المجاميع القديمة صفرًا وثلاثًا، ونضيف سبعًا إلى كل منها، فتصبح السبعة والعشرة ممكنتين أيضًا. صف هذه المرحلة يضم صفرًا وثلاثًا وسبعًا وعشرًا. شهادة السبعة العنصر واحد، وشهادة العشرة العنصر صفر ثم واحد. كل شهادة تستعمل هوية جديدة مرة، وتحافظ على ترتيب العناصر التي دخلت حسابها.

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

السبعة الثانية تصنع أربعة عشر

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

المجاميع حتى الهدف بعد هذه المرحلة هي صفر وثلاث وسبع وعشر وأربع عشرة. قد يكون للسبعة أو العشرة أكثر من شاهد، لكن خانة الوصول تبقى نعم. نحفظ شاهدًا واحدًا بحسب سياسة التنفيذ ولا نستبدله لمجرد وجود نسخة أخرى لها القيمة نفسها. ثم تعالج اثنتا عشرة من العنصر ثلاثة، فتضيف المجموع اثنتي عشرة إلى المجال الذي عرضناه حتى أربعة عشر.

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

صف واحد يحتاج ترتيبًا عكسيًا

إذا ضغطنا الجدول إلى صف منطقي واحد، نريد أن تظل الخانة s ناقص v التي نقرأها تخص المرحلة السابقة. لهذا نعالج المجاميع من الهدف إلى قيمة العنصر نزولًا. عندما نفحص مجموعًا كبيرًا، تكون الخانة الأصغر التي يعتمد عليها لم تحدث بعد بالعنصر الحالي، فتعبر عن الاختيارات التي كانت موجودة قبل استعماله.

خذ عنصرًا واحدًا قيمته ثلاث وحدًا مقداره ستة. في المرور العكسي نفحص الستة قبل الثلاثة؛ حالة الثلاثة القديمة لا، فتظل الستة لا. ثم نصل إلى الثلاثة ونقرأ صفرًا القديم الممكن، فتصبح الثلاثة نعم. انتهت المرحلة بمجموعين فقط، صفر وثلاث، كما يجب لقائمة فيها عنصر واحد لا يستعمل إلا مرة.

أما المرور التصاعدي في صف واحد فيكتب نعم عند ثلاثة أولًا، ثم يقرأها عند ستة فيكتب نعم هناك أيضًا. بهذه القراءة أعاد استعمال العنصر الحالي، وصار يحسب سؤالًا يسمح بالتكرار بدل السؤال المحدود. لا نطلق حكمًا عامًا أن المرور التصاعدي خطأ في كل جدول؛ الخطأ هنا أنه لا يحافظ على اعتماد الصف السابق المطلوب لهذا العقد.

عرض الرسم بالحجم الكامل

اتجاه الصفين ليس اتجاه الصف الواحد

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

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

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

شاهد واحد لا يعني الأقل أو الجميع

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

مثال مستقل بقيم اثنتين وثلاث وخمس وهدف خمس يوضح ذلك: بعد أول عنصرين قد نحفظ الاثنين والثلاثة شاهدًا، ثم يأتي عنصر الخمس المفرد. كلاهما يحقق الهدف، لكن شاهد العنصر الواحد أقصر. تنفيذنا لا يستبدل شاهدًا صحيحًا موجودًا لمجرد أنه وجد شاهدًا أقصر، ولم يدع أنه يحسب الحد الأدنى لعدد العناصر.

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

جميع المجاميع تحتاج حدًا أوسع

جدولنا المصور يتوقف عند أربعة عشر لأنه هدف الشرح. لا يقول إن اثنتي عشرة وأربع عشرة هما أكبر مجموعين من عناصر الأصل؛ فقد أهملنا عمدًا أعمدة أعلى من الحد. بما أن القيم موجبة، يمكن حساب جميع المجاميع حتى مجموعها الكلي تسعة وعشرين إذا أردنا جوابًا أوسع، ثم نقرأ الممكن من ذلك الجدول الجديد.

عند التوسع تظهر المجاميع صفر وثلاث وسبع وعشر واثنتي عشرة وأربع عشرة وخمس عشرة وسبع عشرة وتسع عشرة واثنتين وعشرين وست وعشرين وتسع وعشرين. هذه اثنتا عشرة قيمة مختلفة مع الصفر، أو إحدى عشرة موجبة. لا نعد كل مجموعة فهارس قيمة جديدة إذا أعطت مجموعًا سبق ظهوره؛ المجاميع المتميزة تختلف من عدد مجموعات الاختيار.

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

الفارغ والهدف صفر والقيم المخالفة

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

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

ونراجع نوع الهدف والقيم والحدود قبل البناء؛ عقد الفحص أعداد صحيحة للقيم وهدف صحيح غير سالب، ويرفض النوع المنطقي والعشري. هذه شروط تنفيذ تعليمية، وليست حكمًا بأن كل بيانات تطبيق ينبغي أن تكون بهذه الصورة. نثبت السؤال ونوع البيانات، ثم نختار طريقة مناسبة له، ونميز رفض مدخل مخالف من جواب لا لمجموع صالح لم يظهر.

التغيير في نسخة العناصر يغير الشاهد

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

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

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

حجم الحالة وحدود التبسيط

إذا كان لدينا عدد عناصر n وهدف T، فالجدول الكامل للصفوف المنطقية يعالج حتى T لكل مرحلة، وتزداد مساحة صفوفه مع عدد العناصر والهدف. يمكن تمثيل الإمكانية بصف واحد لتقليل الحفظ، لكن استعادة شاهد تحتاج بيانات أخرى أو سياسة تحفظ علاقة الاختيار. تنفيذنا التعليمي يحتفظ بالشواهد والصفوف للعرض والفحص، فلا نصفه بأنه صف واحد فقط في الذاكرة.

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

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

كيف تحققنا من عدم تكرار الهوية؟

راجعنا 3280 قائمة بأطوال من صفر إلى سبعة وقيم من واحد وثلاث وخمس. لكل قائمة عددنا جميع مجموعات الفهارس مباشرة، وجمعنا القيم التي اختارتها كل مجموعة. قارنّا المجاميع الناتجة بخريطة الشواهد وصفوف الوصول، بما فيها كل بادئة من العناصر. بلغت مقارنات البوادئ 24604، وراجعنا 61854 شاهدًا من حيث صحة الفهارس وتفردها ومجموع القيم.

وقارنّا الصف النهائي بالتحديث العكسي المضغوط، وحفظنا مثال العنصر ثلاث الذي يجعل المرور التصاعدي يزعم الوصول إلى ستة خطأ في العقد المحدود. فحصنا كذلك نسختي السبعة والحد الموسع والقائمة الفارغة ورفض الأنواع والقيم المخالفة. هذه تجارب محدودة، وليست برهانًا تجريبيًا لكل مدخل أو قياس أداء أو قرارًا عن عناصر حقيقية لم نر بياناتها.

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