pro.algorithms
Всем привет, как среди набора элементов найти минимальное количество групп
по N элементов, сумма которых не будет превосходить S?
13 ответов
Александр
Петров
Автор вопроса
Например, есть массив [3,4,6,2,5,6,7,4,3]. В этом наборе стоит задача: найти минимальное количество подмассивов по 3(или меньше) элементов, так, чтобы сумма элементов каждого подмассива не превосходила 12
Например, есть массив [3,4,6,2,5,6,7,4,3]. В этом ...
... и так чтобы объединение этих подмассивов равно массиву, видимо?
Александр
Петров
Автор вопроса
... и так чтобы объединение этих подмассивов равно...
получается, что так)
Например, есть массив [3,4,6,2,5,6,7,4,3]. В этом ...
Вроде жадник же работает, разве нет? (пихаем в текущий, пока влезает и разрешено, потом пихаем в следующий). Доказательство: Пусть есть оптимальное разбиение. Найдём первое несовпадение с жадником, сделаем так, чтобы совпадало, возможно, отобрав немного у следующего (следующих) отрезков. Ответ не стал хуже. Повторим.
Вроде жадник же работает, разве нет? (пихаем в тек...
Из первого описания я понял что элементы не подряд идущие
Например, есть массив [3,4,6,2,5,6,7,4,3]. В этом ...
Так подмассив (отрезок элементов, массив, получающийся удалением некоторого количества (возможно, нуля) элементов из начала и некоторого количества из конца) или подпоследовательность (элементы на произвольном подмножестве индексов массива)?
Александр
Петров
Автор вопроса
Так подмассив (отрезок элементов, массив, получающ...
Подмассив - провафлил с названием. Виноват. Просто набор любых элементов из заданного
Кажется, обычная задача на несколько одинаковых рюкзаков, решается так же, только нужно в параметре хранить оставшееся место в незаполненном рюкзаке
Или я чего-то не понимаю или тут рюкзак вообще не нужен
Похожие вопросы
Обсуждают сегодня