![down-syndrome-young-man-with-teacher-building-lego-blocks-D[...].jpg](https://2ch.life//math/src/34835/15159348417470.jpg)
131 Кб, 1300x936Секите задачку, пацанчики.
Есть у нас сколько-то фигурок. Известно, сколько из них какого цвета (N цветов) и сколько какой формы (M форм).
Как бы так найти минимальное количество сочетаний цвет-форма, на которые их все можно поделить?
Есть у нас сколько-то фигурок. Известно, сколько из них какого цвета (N цветов) и сколько какой формы (M форм).
Как бы так найти минимальное количество сочетаний цвет-форма, на которые их все можно поделить?
Я тут подумал и вроде это сводится N+M линейных уравнений на NM переменных, решением которого является подпространство размерности NM-N-M или типа того, и нам из этого подпространства надо такую точку, чтоб все координаты были целыми, и чтоб ещё на пересечении с плоскостями вида xi=0.
Может это известная проблема и даже название есть?
Может это известная проблема и даже название есть?
известно только кол-во фигурок с конкретным цветом/формой или мы знаем про набор фигурок всё, т.е. сколько зелёных шаров и т.д. ?
>Как бы так найти минимальное количество сочетаний цвет-форма, на которые их все можно поделить?
так у тебя там не должно быть минимума. введи на множестве своих фигурок разноцветных отношение эквивалентности "фигурки эквивалентны, если у них одинаковая форма и цвет". очевидно, что это отн. эквивалентности и оно однозначно твоё множество разобьет на набор непересекающихся подмножеств. и ты хоть хуй соси, если хочешь рассказать человеку обо всем своём ассортименте фигурок, должен будешь перечислить все "имена" наборов.
>>5199
первое известно, второе надо предложить, но так, чтоб кол-в групп было минимально.
>>5201
Нене, если сказано что 3 красных и 3 синих, 3 квадрата и 3 треугольника, могут быть 3 красных треугольника и 3 синих квадрата, а могут быть 3 красных квадрата и 3 синих треугольника.
На самом деле, как оказалась, эта задача в духе subset sum, нп-полная, как решать понятно.
В худшем случае N+M-1 групп, в лучшем max(n,m).
первое известно, второе надо предложить, но так, чтоб кол-в групп было минимально.
>>5201
Нене, если сказано что 3 красных и 3 синих, 3 квадрата и 3 треугольника, могут быть 3 красных треугольника и 3 синих квадрата, а могут быть 3 красных квадрата и 3 синих треугольника.
На самом деле, как оказалась, эта задача в духе subset sum, нп-полная, как решать понятно.
В худшем случае N+M-1 групп, в лучшем max(n,m).
>>4835 (OP)
Я тебя нихуя не понял.
MxN - все комбинации цвет-форма.
Потом делим все имеющися фигурки на MN и получаем число фигурок каждой вариации, поровну.
Округляем до целых в одну из сторон, но конечная сумма всех должна совпасть с количеством фигурок.
Я тебя нихуя не понял.
MxN - все комбинации цвет-форма.
Потом делим все имеющися фигурки на MN и получаем число фигурок каждой вариации, поровну.
Округляем до целых в одну из сторон, но конечная сумма всех должна совпасть с количеством фигурок.