الخوارزمية التي هي مزيج من مشكلة Quapsack المستمرة ومشكلة تعبئة صندوق الحجم المتغير

Question

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

مثال: دفع الشخص أ 100 دولار

لقد دفع الشخص ب 200 دولار

لقد دفع الشخص C 50 دولارًا

الشخص D سيدفع 24 دولارًا

الشخص E سيدفع 175 دولارًا

الشخص F سيدفع 151 دولارًا

أحد الحلول الممكنة لهذا هو

الشخص E يدفع 100 دولار للشخص أ ،

الشخص E يدفع 75 دولار للشخص ب ،

يدفع الشخص F 125 دولارًا للشخص ب ،

الشخص و يدفع 26 دولارًا إلى شخص ج

يدفع الشخص D 24 دولارًا إلى شخص ج

Answer 1

من الناحية النظرية ، يمكن تأطير هذا كمشكلة تحسين:

في الأساس ، سنقوم بإنشاء مجموعة من القيود التي تعدد بنية مشكلتك ، وبذرة القيم الأولية ، وتأكد من أننا نخصص كل الأموال كما أشرت.

قيود الحالة الأولية:

A_paid = 100
B_paid = 200
C_paid = 50
D_out  = 24
E_out  = 175
F_out  = 151

لا يمكن أن يتجاوز المبلغ المدفوع المبلغ المتاح: (نحدد D_to_A كمتغير يحمل المبلغ المدفوع من الشخص D إلى شخص A)

D_out >= D_to_A + D_to_B + D_to_C
E_out >= E_to_A + E_to_B + E_to_C
F_out >= F_to_A + F_to_B + F_to_C

يجب أن يكون المبلغ المدفوع لكل فرد مساوياً لما دفعوه بالفعل:

A_paid = D_to_A + E_to_A + F_to_A
B_paid = D_to_B + E_to_B + F_to_B
C_paid = D_to_C + E_to_C + F_to_C

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

min: D_to_A + D_to_B + D_to_C + ...

يمكنك استخدام تقنية التحسين المفضلة لديك لحل المشكلة ، وهناك الكثير من حلول البرامج الخطية المتاحة ، أحب LPSOLVE.

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