تحتاج الخوارزمية إلى مجموعة الملفات من الأحجام المختلفة في كتل متساوية تقريبا

Question

أحاول معرفة الخوارزمية التي ستساعدني في مجموعة متنوعة من الملفات ذات الأحجام المختلفة في القول، "N" من الحجم المتساوي تقريبا.

أي أفكار حول كيفية تحقيق هذا؟

Answer 1

Find the target group size. This is the sum of all sizes divided by n.
Create a list of sizes.
Sort the files decreasing in size. 
for each group
    while the remaining space in your group is bigger than the first element of the list
        take the first element of the list and move it to the group
    for each element
        find the elemnet for which the difference between group size and target group size is minimal
    move this elemnt to the group

هذا لا ينتج نتائج مثالية، ولكن من السهل تنفيذها وتحصل على نتائج جيدة. الحل الأمثل، تحتاج إلى بحث شامل وهو NP Complete.

Answer 2

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

Answer 3

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

netlib لديه هذا كود فورتران لحل مشكلة أكثر عمومية بعدة اليدين (العناصر لها ربح وكذلك قيم التكلفة / الوزن).