Три кучи равной массы

@mangomang · Регистрация: 06.10.2020

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

Дан набор гирек массой m1, …, mN. Разделите его на три кучки равной массы, содержащие равное число гирек.

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Примеры
входные данные

Code
1
2
6
10 20 30 40 50 60

выходные данные

Понимаю, как решать, когда две кучи. Для трех вообще нет идей.

@codcw · 28.03.2021, 03:36

mangomang, мои мысли примерно на этом остановились

Python
1
2
3
4
5
from itertools import product
b = [50,1,20,31,10,41]
a = list(set([frozenset(i) for i in product(b,b) if len(frozenset(i))==2]))
c = [i for i,j in enumerate(map(sum, a)) if j==51]
print(*[a[i] for i in c])

хз как избавиться от костылей в виде сетов и продакта, нужно перебором достать комбинации, а я слишком тупой чтоб додуматься как это сделать без костылей

Добавлено через 3 минуты
тут та же задача, но описан только алгоритм, и то недостаточно подробно
Разбить последовательность чисел на три набора с равной суммой

тип задачи, если я правильно понял, "Мультипликативный рюкзак", но не с максимизацией сумм, а с конкретной равной суммой
всё что нагуглил по теме слишком сложно T_T
так что что есть то есть

@Arsegg · 28.03.2021, 10:35

codcw, перебором задачу не решить, 18! - слишком много и долго для перебора. Тут скорее всего какая-то хитрая динамика должна быть, типа кубической. А так да, по сути, нужно собрать 3 рюкзака с равным весом.

@Gdez · 28.03.2021, 13:37

Arsegg, почему 18! ?
Получается для самого "затратного" чуть больше 18,5 тысяч вариантов - 18!|(12!*6!)

@Arsegg · 28.03.2021, 14:07

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

12!*6!

344881152000 - все равно много для перебора.
/upd

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

почему 18! ?

Ну я очень грубо выразился, мой фейл. Надо было писать O(N!).

/upd2
Здесь разбор на leetcode: 698. Partition to K Equal Sum Subsets.
P. S. Лениво разбираться в коде рюкзаков.

@Gdez · 28.03.2021, 14:36

Arsegg, я не точно написал - 18!/(12!*6!) = 18564 варианта

Добавлено через 7 минут
Вроде по условию - равные по количеству и равные по сумме. Значит общее количество может быть только одним из - 3, 6, 9, 12, 15, 18 и в каждой "куче" соответственно 1, 2, 3, 4, 5, 6.
Формируешь массив от 0 до n-1 натуральных чисел. Генерируешь перебор всех вариантов по n//3 в каждом.
Через индексацию numpy ищется сумма каждого набора с удалением не равных (сумма всех гирек) / 3.
Как то так можно...
...
В общем тоже лень

@Arsegg · 28.03.2021, 14:48

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

В общем тоже лень

Хз, переборы, как и их эвристики (брут-форс) для NP-полных задач - такое себе. А погружаться в задачу, когда ТС пальцем о палец не ударил в сторону самостоятельного решения - не возникает абсолютно никакого желания.

@user-ganz · 28.03.2021, 15:04

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
alfa=[1,2,3,4,5,6]
alfa.sort()
 
left,cntr,right=[],[],[]
lefta,righta=[],[]
bravo=round(len(alfa)/3) #heap
 
lefta=alfa[:bravo]
cntr=alfa[bravo:bravo*2]
righta=alfa[bravo*2:]
 
righta.reverse()
 
for it in range(len(lefta)):
    if it%2:
        left.append(lefta[it])
        left.append(righta[it])
    else:
        right.append(lefta[it])
        right.append(righta[it])
 
print(left,cntr,right)
print(sum(left),sum(cntr),sum(right))

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

но код может быть более элегантным, точнее должен быть

@Arsegg · 28.03.2021, 16:26

user-ganz2, чет мне подсказывает, что жадником (жадным алгоритмом) задачу о 0-1 рюкзаке не решить. Хотя могу ошибаться.

@user-ganz · 28.03.2021, 16:54

Arsegg, тоже казалось так же в начале, что есть некая комбинация которая "сломает" логику, но вроде, работает... если изначально комбинация разрешима

@Arsegg · 28.03.2021, 16:59

Сообщение от user-ganz2

но вроде, работает...

Глянь теорию: Решение задачи о сумме подмножеств.
P. S. Понимаю, если бы ты упомянул генетический алгоритм, но жадник, мне кажется, в общем случае дает неверное решение (сложно с ходу придумать контрпример).

@user-ganz · 28.03.2021, 17:54

Arsegg, не указано же, что генетический являятся единственно верным..
пусть дано множество из 6 элементов, которые равны 1.
пусть нужно увеличить один элемент на 1, но по условия задачи мы одновременно должны увеличить ещё два те 111222
пусть нужно уменьшить один элемент на 2, по условиям задачи уменьшаем ещё два, 111000\11-1002\-1-1-1222
то есть теорема доказана для n и для n+1 следовательно решение приемлимое

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	28.03.2021, 10:35
	codcw, перебором задачу не решить, 18! - слишком много и долго для перебора. Тут скорее всего какая-то хитрая динамика должна быть, типа кубической. А так да, по сути, нужно собрать 3 рюкзака с равным весом. 0

@Gdez 8850 / 4501 / 1864 Регистрация: 27.03.2020 Сообщений: 7,316
	28.03.2021, 13:37
	Arsegg, почему 18! ? Получается для самого "затратного" чуть больше 18,5 тысяч вариантов - 18!\|(12!*6!) 0

@Gdez 8850 / 4501 / 1864 Регистрация: 27.03.2020 Сообщений: 7,316
	28.03.2021, 14:36
	Arsegg, я не точно написал - 18!/(12!6!) = 18564 варианта Добавлено через 7 минут* Вроде по условию - равные по количеству и равные по сумме. Значит общее количество может быть только одним из - 3, 6, 9, 12, 15, 18 и в каждой "куче" соответственно 1, 2, 3, 4, 5, 6. Формируешь массив от 0 до n-1 натуральных чисел. Генерируешь перебор всех вариантов по n//3 в каждом. Через индексацию numpy ищется сумма каждого набора с удалением не равных (сумма всех гирек) / 3. Как то так можно... ... В общем тоже лень 0

@Arsegg 3582 / 2182 / 571 Регистрация: 02.09.2015 Сообщений: 5,510
	28.03.2021, 16:26
	user-ganz2, чет мне подсказывает, что жадником (жадным алгоритмом) задачу о 0-1 рюкзаке не решить. Хотя могу ошибаться. 0

@user-ganz Костыли любой сложности 201 / 146 / 36 Регистрация: 27.10.2019 Сообщений: 843
	28.03.2021, 16:54
	Arsegg, тоже казалось так же в начале, что есть некая комбинация которая "сломает" логику, но вроде, работает... если изначально комбинация разрешима 0

@user-ganz Костыли любой сложности 201 / 146 / 36 Регистрация: 27.10.2019 Сообщений: 843
	28.03.2021, 17:54
	Arsegg, не указано же, что генетический являятся единственно верным.. пусть дано множество из 6 элементов, которые равны 1. пусть нужно увеличить один элемент на 1, но по условия задачи мы одновременно должны увеличить ещё два те 111222 пусть нужно уменьшить один элемент на 2, по условиям задачи уменьшаем ещё два, 111000\11-1002\-1-1-1222 то есть теорема доказана для n и для n+1 следовательно решение приемлимое 0