Задача поиска подмножеств с минимальной суммой Amazon

@munchkin · Регистрация: 01.05.2021

Студворк — интернет-сервис помощи студентам

Есть список задач - массив чисел. Каждое число представляет собой сложность задачи. Задачи идут в строгом порядке, который нельзя менять. Так же дано количество дней. Сложность дня определяется самой сложной задачей, решенной в этот день.  Нужно написать функцию, которая разобьет задачи по дням так, чтобы общая сложность (сумма) было минимальная.  

Пример 1: 
Задачи [3, 1, 4, 2, 5]
2 дня.

Решение: 
первый день [3] -> 3,  
второй день [1, 4, 2, 5] -> 5 (т.к. Сложность дня определяется самой сложной задачей)
3 +5 = 8

Пример 2: 
Задачи [2, 4, 7, 3, 5, 1, 6]
3 дня.

Решение: 
первый день [2] -> 2,
 второй день [4] -> 4
Третий день [73516] -> 7
2+ 4 + 7 = 13

Ищу идеи для решения сложностью меньше O(n^m)

@Shamil1 · 08.05.2021, 12:28

vrm2,
Я взял цикл из твоей программы, только вместо переменной end использую k = end - start.

@Nacuott · 12.06.2021, 10:46

Сообщение от munchkin

Каждое число представляет собой сложность задачи. Задачи идут в строгом порядке, который нельзя менять.

Как понимать это требование. Ведь оно ни разу не использовалось в приведенных алгоритмах?

@vrm2 · 12.06.2021, 12:07

Сообщение от Nacuott

Как понимать это требование. Ведь оно ни разу не использовалось в приведенных алгоритмах?

Так и понимать, что порядок задач в списке менять нельзя. Т.е. список задач представляет именно список, и нам его надо разрезать на n частей.

Если задачи можно менять местами, что решение становится простым - сортируем задачи, затем на каждый день ставим самую легкую задачу, а на последний день - оставшиеся задачи.

Задачи [2, 4, 7, 3, 5, 1, 6]
3 дня.
Ответ [{1}, {2}, {3,4,5,6,7}] => 1 + 2 + 7 = 10

@vantfiles · 12.06.2021, 14:49

Сообщение от munchkin

Ищу идеи для решения сложностью меньше O(n^m)

Откуда такое большое число?

Пусть M - количество задач, N - количество дней.

Тогда количество вариантов разбивок будет равно n = n * ( n + 1) / 2, где n = M - N + 1

Множим на число циклов поиска суммы максимумов - и как-то все равно получается чуточку меньше...

Добавлено через 11 минут
то есть просто максимумов

@Nacuott · 12.06.2021, 15:56

Сообщение от vrm2

Так и понимать, что порядок задач в списке менять нельзя. Т.е. список задач представляет именно список, и нам его надо разрезать на n частей.

Ясно, но из условия задачи это не очевидно.

@vrm2 · 13.06.2021, 14:39

Сообщение от vantfiles

Откуда такое большое число?

Если имеем N задач и K дней, то у нас есть (N-1) мест, где мы можем разрезать список, из которых нужно выбрать (K-1).

Количество возможных вариантов по формуле сочетаний равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?C^{k-1}_{n-1}$ , что близко к n^k

@vantfiles · 13.06.2021, 18:01

Сообщение от vrm2

Количество возможных вариантов

м??

@vrm2 · 14.06.2021, 00:57

Сообщение от vantfiles

м??

Что "м??"

@vantfiles · 14.06.2021, 07:27

Сообщение от vrm2

Если имеем N задач и K дней, то у нас есть (N-1) мест

K-1

Добавлено через 3 минуты

Кликните здесь для просмотра всего текста

1 2 3 4 5 6 7 8 9

1 1 7
1 2 6
1 3 5
1 4 4
1 5 3
1 6 2
1 7 1
2 1 6
2 2 5
2 3 4
2 4 3
2 5 2
2 6 1
3 1 5
3 2 4
3 3 3
3 4 2
3 5 1
4 1 4
4 2 3
4 3 2
4 4 1
5 1 3
5 2 2
5 3 1
6 1 2
6 2 1
7 1 1

9 3 -- 28

Это далеко не 9^3

@vrm2 · 14.06.2021, 14:42

Сообщение от vantfiles

K-1

Нет, все верно. У нас есть (N-1) мест, где мы можем разрезать список. А не (K-1).

Могли бы Вы отвечать более развернуто? По междометиям и односложным ответам трудно понять мысль, которую хочет донести собеседник.

Сообщение от vantfiles

Это далеко не 9^3

В вики https://en.wikipedia.org/wiki/Binomial_coefficient в разделе "Bounds and asymptotic formulas" указаны формулы асимптот. Например, можно рассмотреть случай: 1000 задач, 10 дней.

@Shamil1 · 14.06.2021, 15:25

Сообщение от vantfiles

9 3 -- 28

8!/(6!*2!) = 8*7/2 = 28

Сообщение от vantfiles

Пусть M - количество задач, N - количество дней.
Тогда количество вариантов разбивок будет равно n = n * ( n + 1) / 2, где n = M - N + 1

Максимум n достигается при N=1? При N=1 у нас 1 вариант разбиения (все задачи в один день).

@vantfiles · 18.06.2021, 14:19

Сообщение от Shamil1

8!/(6!*2!) = 8*7/2 = 28

Shamil1, да, формулу я вывел неверно. Не могли бы пояснить свою? Как от факториалов произошел переход к таким малым числам?

Добавлено через 35 минут

Сообщение от vrm2

что близко к n^k

1000 задач и 1000 дней -- это один вариант. Откуда n^k ?

Добавлено через 9 минут
Такое ощущение, что здесь имеет место гауссово распределение, но доказать я это не могу

Добавлено через 12 минут
а, формула n! / ( k! * ( n - k )! )

ну очевидно же, что это далеко не n^k

ну да, нормальное распределение... Первый раз такое вижу для сложности алгоритма...

Добавлено через 8 минут
нет, тоже не сходится...

Добавлено через 56 секунд
Коллеги, кто-нибудь может показать правильную формулу для количества вариантов разбиений?

@Shamil1 · 18.06.2021, 16:50

Сообщение от vantfiles

Не могли бы пояснить свою?

Количество способов выбрать (K-1) "мест между задачами" из (N-1) "мест между задачами":

Сообщение от vrm2

Если имеем N задач и K дней, то у нас есть (N-1) мест, где мы можем разрезать список, из которых нужно выбрать (K-1).

Сообщение от vantfiles

ну очевидно же, что это далеко не n^k

Максимальное значение при k = n/2 при больших n примерно равно:
2ⁿ/sqrt(n*PI/2)
Это не n^k, но всё равно много.

@vrm2 · 18.06.2021, 17:07

Сообщение от vantfiles

а, формула n! / ( k! * ( n - k )! )

Эту формулу я и приводил Вам ранее - это формула количества сочетаний C(n;k).

Сообщение от vantfiles

ну очевидно же, что это далеко не n^k

Также давал ссылку на формулы асимптот для этой функции C(n;k)
n^k - одни из вариантов асимптоты, точнее n^k / k!

Например для больших n и маленьких k реальное значение будет много ближе к n^k, чем к n^2, предложенное Вами.
Для того, чтобы Вы могли убедиться в этом, я и предложил рассмотреть случай n=1000 и k=10

@vantfiles · 18.06.2021, 17:15

Сообщение от Shamil1

Если имеем N задач и K дней, то у нас есть (N-1) мест, где мы можем разрезать список, из которых нужно выбрать (K-1).

А вот это ничего не меняет:

Сообщение от munchkin

Задачи идут в строгом порядке, который нельзя менять.

?

Добавлено через 2 минуты

Сообщение от vrm2

это формула количества сочетаний C(n;k).

С учетом запрета на изменение порядка задач эта формула остается?

@Shamil1 · 18.06.2021, 17:25

Сообщение от vantfiles

А вот это ничего не меняет:

Это учитвается. N задач - поэтому N-1 "мест между задачами". И в любом из них мы можем закончить очередной день.

Сообщение от vrm2

Например для больших n и маленьких k реальное значение будет много ближе к n^k,

Для маленьких k неинтересно. Например, для k=2 имеем n^k = n²

@vantfiles · 18.06.2021, 17:44

Сообщение от Shamil1

И в любом из них мы можем закончить очередной день.

10 задач, 3 дня. В первый день выполняем 9 задач. Дальше как разбиваем?

Добавлено через 11 минут

Сообщение от Shamil1

Например, для k=2 имеем n^k = n²

4 задачи, 3 дня. Разбивки:

112
121
211

Что с формулой не так?

@vrm2 · 18.06.2021, 18:41

Сообщение от vantfiles

4 задачи, 3 дня. Разбивки:
112
121
211
Что с формулой не так?

С формулой все так. Количество равно 3! / (2! * (3-2)!) = 6 / (2*1) = 3

P.S. Нужно читать не только ответ Shamil1, но и контекст, в котором ответ дан

@Shamil1 · 18.06.2021, 20:55

Сообщение от vantfiles

10 задач, 3 дня. В первый день выполняем 9 задач. Дальше как разбиваем?

В первый день выполнить 9 задач не получится.

9!/(7!*2!)
У нас есть 9 ямок, в которые можно положить 2 мячика. Сначала раскладываем мячики по ямкам, а потом считаем, сколько там задач получилось в первый день.

Добавлено через 26 минут

Сообщение от vantfiles

Что с формулой не так?

Ваша формула верна для трех дней.
(M-1)!/(M-1-2)!/2! = (M-1)(M-2)/2 = n * ( n + 1) / 2, где n = M - 3 + 1

@vantfiles · 19.06.2021, 14:24

Shamil1, vrm2, не сочтите за занудство, я реально не могу понять ваши выкладки.

Сообщение от vrm2

С формулой все так. Количество равно 3! / (2! * (3-2)!) = 6 / (2*1) = 3

Объясните, пожалуйста, в какую формулу и что именно Вы подставляете.
Откуда при "4 задачи, 3 дня." в формуле появляется двойка?

Сообщение от Shamil1

У нас есть 9 ямок, в которые можно положить 2 мячика.

Хорошая аналогия. Вот только у нас есть 3 ямки и 10 мячиков. И еще нельзя менять порядок их раскладки.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@munchkin 0 / 0 / 0 Регистрация: 01.05.2021 Сообщений: 5

	Задача поиска подмножеств с минимальной суммой Amazon 01.05.2021, 16:22. Показов 4868. Ответов 41 Метки amazon (Все метки) Есть список задач - массив чисел. Каждое число представляет собой сложность задачи. Задачи идут в строгом порядке, который нельзя менять. Так же дано количество дней. Сложность дня определяется самой сложной задачей, решенной в этот день.  Нужно написать функцию, которая разобьет задачи по дням так, чтобы общая сложность (сумма) было минимальная.   Пример 1:  Задачи [3, 1, 4, 2, 5] 2 дня. Решение:  первый день [3] -> 3,   второй день [1, 4, 2, 5] -> 5 (т.к. Сложность дня определяется самой сложной задачей) 3 +5 = 8 Пример 2:  Задачи [2, 4, 7, 3, 5, 1, 6] 3 дня. Решение:  первый день [2] -> 2,  второй день [4] -> 4 Третий день [73516] -> 7 2+ 4 + 7 = 13 Ищу идеи для решения сложностью меньше O(n^m) 0

@Shamil1 Модератор 3140 / 2288 / 469 Регистрация: 26.03.2015 Сообщений: 8,898
	08.05.2021, 12:28
	vrm2, Я взял цикл из твоей программы, только вместо переменной end использую k = end - start. 0