MySQL العثور على المجموعات الفرعية

Question

تعديل:

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

فاتورة حصلت على 100 دولار بقيمة البنود من متجر.

يريد إعادة ما يكفي من العناصر للحصول على 30 دولار بالضبط.

يحتوي المتجر على نقطة عودة نظام سيساعده في القيام بذلك.

هنا هي البيانات بعد أن يقوم بمسح عناصره:

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

ربما فاتني بعض الخيارات، منذ أن صنعت كل هذا.

لذلك، السؤال الكبير هو:

هل هناك طريقة (مع المجموعة، ربما) للحصول على استعلام واحد من شأنه أن يعيد مزيجا ممكنا من أي وقت مضى من العناصر؟

شكرا!

أ

Answer 1

إذا كان عدد العناصر الصغيرة بما يكفي، فيمكنك القوة الغاشمة مع SQL. قد يكون هذا هو الحل سريعا لكتابة، ولكن ربما تريد أن تفعل شيئا أكثر ذكاء. يبدو وكأنه "مشكلة napsack"أي NP كاملة.

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

إذا كان عدد العناصر صغيرا نسبيا، فقد تكون قادرا على القوة الغاشمة. عبارة SQL Force الضخمة (التي طلبت) التي تجد مجموعات من 1،2 أو 3 عناصر تتطابق كما يلي. إذا لم يكن هذا مرضا، فربما لا تكون SQL الأداة المناسبة لهذه المهمة.

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

في Oracle، ستستخدم وظيفة المكعب لتحويل هذا إلى إصدار عام، غير متأكد من مكافئ MySQL.

Answer 2

أنت تطلب جميع المجموعات الفرعية التي تبلغ 30 دولارا تماما.

هذا يبدو كثيرا مثل مشكلة فرعية مجموع, ، و مشكلة napsack, ، لذلك أشك بشدة في القيام بذلك باستخدام استفسار بسيط. من المحتمل أن تتحول إلى T-SQL، ولكن حتى ذلك ربما تبدو قبيحة.

أعتقد أن البرمجة هي الطريقة للذهاب هنا.

Answer 3

لا أعتقد أن المجموعة من خلال القيام بذلك.

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

إذا كان لديك عناصر أكثر من 30 دولار، فيمكنك حذفها.

سيكون هناك بعض التحسينات إذا كنت تريد خيار "أفضل" من خلال بعض المعايير.

Answer 4

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

يمكنك استخدام بعض الخوارزميات الموجودة التي يمكن أن تعطيك تخمين جيد جدا، لكنني أخشى أنهم جميعا من غير SQL.

أود أن أقترح القيام بتقريب مشكلتك:

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