أقل عدد قطع لتكوين هدف صحيح: جدول الحالات واستعادة الاختيار

هدف مساواة المجموع مع أقل عدد

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

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

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

[1]

أحجام واحد وثلاثة وأربعة وهدف ستة

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

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

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

الأكبر أولًا لا يكفي في المثال

قاعدة اختيار أكبر حجم لا يتجاوز الباقي تبدأ بالقطعة 4 عند هدف 6. يبقى 2، ولا يناسبه حجم 3 أو4، فتأخذ 1 ثم 1. انتهت القاعدة إلى ثلاث قطع ومجموع صحيح. لكنها لم تنتج أقل عدد، لأن البديل 3 ثم 3 أعطى المجموع نفسه بقطعتين. نجاح الوصول وحده لم يكف لإثبات الأمثلية.

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

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

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

حالة الصفر والغياب عن التكوين

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

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

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

العلاقة بين الحالة والباقي

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

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

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

ترتيب البناء من الأصغر إلى الهدف

نبني الحالات تصاعديًا من واحد حتى ستة بعد تثبيت الصفر. كل باقٍ x ناقص c أصغر من x لأن c موجب، ولذلك تكون حالته قد حسبت قبل أن نحتاجها. لا نقرأ حالة مستقبلية لم تكتمل، ولا نفترض أن قيمة افتراضية غير معلومة هي أفضل عدد. ترتيب البناء جزء من صحة استعمال جدول البواقي.

عند الهدف واحد يتاح الحجم 1 وحده فيعطي العدد واحدًا. وعند اثنين تعطي قطعتان من 1 العدد اثنين. ثم عند ثلاثة يكون الحجم 3 نفسه أفضل من تكرار 1 ثلاث مرات، وعند أربعة يكفي الحجم 4. لا تتبع أعداد الحالات زيادة واحدة دائمًا؛ دخول حجم متاح كامل قد يخفض العدد مقارنةً بالهدف الأصغر قبله.

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

جدول الحالات حتى ستة

القيم النهائية من هدف صفر إلى ستة هي 0 ثم 1 ثم 2 ثم 1 ثم 1 ثم 2 ثم 2. عند خمسة يوجد تكوين 1 مع 4 بقطعتين، وعند ستة تكوين 3 مع 3 بقطعتين. الجدول يخزن الأعداد الدنيا فقط؛ معرفة أن الحالة خمسة عددها اثنان لا تحدد من نفسها أي حجمين اخترناهما.

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

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

استعادة القطع من قرار الحالة

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

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

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

التعادل لا يعني جميع التكوينات

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

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

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

الكود الأصلي وتوحيد الأحجام

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

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

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

def minimum_pieces(target, sizes):
    if type(target) is not int:
        raise TypeError("integer target required")
    if target < 0:
        raise ValueError("nonnegative target required")
    original = tuple(sizes)
    if any(type(size) is not int for size in original):
        raise TypeError("integer sizes required")
    if any(size <= 0 for size in original):
        raise ValueError("positive sizes required")
    available = tuple(sorted(set(original)))
    best = [None] * (target + 1)
    choice = [None] * (target + 1)
    best[0] = 0
    for total in range(1, target + 1):
        for size in available:
            if size <= total and best[total - size] is not None:
                candidate = best[total - size] + 1
                if best[total] is None or candidate < best[total]:
                    best[total] = candidate
                    choice[total] = size
    pieces = None
    if best[target] is not None:
        pieces = []
        remaining = target
        while remaining:
            size = choice[remaining]
            pieces.append(size)
            remaining -= size
        pieces = tuple(pieces)
    return {"count": best[target], "pieces": pieces, "table": tuple(best)}

الحجم الصفري والسالب خارج العقد

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

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

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

المخزون المحدود وعد الطرق يغيران السؤال

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

وقد يريد سؤال آخر عدد التكوينات الممكنة بدل أقل عدد من القطع. عند هدف ثلاثة بأحجام 1 و3، يوجد التكوين 3 والتكوين 1 ثم 1 ثم 1، بينما أقل عدد هو واحد. خانة الجدول التي تحوي واحدًا لا تقول إن هناك طريقة واحدة فقط؛ هي تحوي قيمة الهدف التحسيني الذي أعلنّاه.

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

مرجع مستقل وفحوص الجدول

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

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

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

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

يمكن وصف الناتج ببطاقة: الهدف ستة، والأحجام 1 و3 و4 مع إعادة استعمال غير محدودة، والمطلوب مساواة دقيقة بأقل عدد. نكتب الجدول 0 و1 و2 و1 و1 و2 و2، والشاهد 3 ثم 3، والعدد اثنين. نضيف أن السياسة تحفظ شاهدًا واحدًا عند التعادل، فلا يحاول القارئ استعادة كل الطرق من قرار واحد لكل حالة.

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

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