Как сгруппировать массив?

Question

[site_trouble]

Добрый день. Есть массив из чисел:
[6, 4, 4, 3, 2, 1.5, 1, 0.5]
Нужно разгруппировать по рядам так, чтобы в каждом ряду сумма чисел была не больше 6.
Получится должно что то вроде этого:

[6]
[4, 2]
[4, 1.5, 0.5]
[3,1]

Есть идеи как это можно сделать? Может есть алгоритмы готовые для данной задачи?

Comments

[Александр]

Тебе любой набор подойдет? Или нужно оптимально распределить?

[site_trouble]

Minifets, оптимально

[Дмитрий]

@site_trouble
1. Под оптимально подразумевается минимальное количество подгрупп?
2. Что важнее, равномерность по всем рядам или побольше максимально близких к 6 при минимальном количестве сильно не дотягивающих до 6?...
например: [4, 3, 2, 1] --> [[4, 1], [3, 2]] vs [[4, 2], [3, 1]] - т.е., в сумме 5 и 5 против 6 и 4

[site_trouble]

Дмитрий, второе важнее

[Дмитрий]

site_trouble, если принципиально, чтобы каждый ряд был как можно ближе к 6, то я бы предложил такой подход (оговорка: не до конца уверен, что это будет самое оптимальное разбиение)

0) сортируем массив (если он по условию не отсортирован);
1) берём максимальный элемент и вычисляем разницу его с шестёркой;
2) полученную недостачу ищем среди оставшихся;
3) если такой отсутствует, формируем подмассив с элементами, не превышающими эту разницу;
4) запоминаем сумму выбранного элемента с максимальным в подмассиве;
5) далее узнаём суммы для всех сочетаний по двое (по трое и т.д.) из элементов подмассива (если их приемлемое количество*) - и либо находим c суммой 6, либо выбираем ближайшее;
6) исключаем выбранные элементы из исходного массива и формируем очередную подгруппу - после чего переходим к следующему максимальному (см. п. 1).
==
* - формула для произвольноко k и для k = 2 и 3

Answer 1

[Дмитрий]

К моему "алгоритму" из комментариев, могу привести такой код на python:
(я видел, что вопрос с тегом "JAVASCRIPT", но лучше так, чем вовсе без кода)

from itertools import combinations

def ungroup(data_list, limit):
    data_list.sort()
    result_list = []
    while sum(data_list) > limit:
        series = [data_list.pop()]
        rest = limit - series[0]
        if rest == 0:
            result_list.append(series)
        elif rest in data_list:
            result_list.append(series + [data_list.pop(data_list.index(rest))])
        else:
            sublist = data_list.copy()
            for i in data_list:
                if i > rest:
                    sublist = data_list[:data_list.index(i)]
                    break
            for n in range(2, len(sublist)):
                comb = {sum(i): i for i in combinations(sublist, n)}
                if rest in comb.keys():
                    series.extend(comb[rest])
                    for i in comb[rest]: data_list.remove(i)
                    break
            result_list.append(series)
    if len(data_list) > 0:
        result_list.append(data_list)
    return result_list

print(ungroup([6, 4, 4, 3, 2, 1.5, 1, 0.5], 6))
# [[6], [4, 2], [4, 0.5, 1.5], [1, 3]]

Comments

[Дмитрий]

Должен оговориться: в коде отсутствует фрагмент описанный в п.п. 4-5 из комментариев к вопросу - т.е. согласно его мы лишь "находим c суммой 6" но не "выбираем ближайшее". Иными словами, если бы в исходном ряду вместо 1.5 было 1.4, подряд [4, 0.5, 1.4] не сформировался бы, поскольку результат сочетания (0.5, 1.4) не обладает суммой rest=2, и в result_list пошёл бы только подряд [4] (сочетание (0.5, 1.4) к нему добавлено бы так и не было).

Добавление этого блока кода усложнило бы восприятие идеи целиком - а целью у меня было лишь проиллюстрировать идею из комментария.

Так что предупреждаю, СКРИПТ НЕПОЛНЫЙ и требует указанной доработки.

[site_trouble]

Дмитрий, добрый день. Цифры в массиве всегда кратны одному и тому же числа, в данном случае - это 0.5.

[Дмитрий]

site_trouble, было бы лучше указать это сразу: исчерпывающее условие делает ответ более структурированным - очень нехвататло так же данных о преимущественной длинне массива (если в нём всегда не больше дюжины элементов, то и подход может быть куда как проще)