Вопрос не достаточно конкретизирован. Предположу, что автор имеет ввиду следующее:
Пусть задан набор слов из N:

Пусть задано число M (== 16). Необходимо найти такие номера слов, что их суммарная длина будет равна M.
Решение 1
Заметим, что слова, как объекты нас не интересуют. Нам интересны лишь их длины. Длины их обозначим через l_i
. Т.е. теперь у нас есть последовательность длин слов (их даже следует назвать множеством):

Математически строго поставим задачу (к решению имеет косвенное отношение).
В таком случае, нам нужно понять, существует ли решение хотя бы одного уравнения A_k
над нашим множеством X
:

Т.е. существует ли решение уравнения

или

и т.д.
x_i
может принимать значения из множества X
ограниченное число раз.
Продолжение решения
Нам нужно найти комбинацию l_i
, которые в сумме дадут M
.
Отсортируем последовательность

по убыванию и выбросим все те, для которых:
,
так как они не смогут участвовать в финальной сумме. После сортировки имеем:
,
где
.
Теперь нам нужно перебрать все варианты решения (т.к. M=16
, т.е. небольшое, то мы в полне уложимся в перебор). Для перебора будем использовать DFS.
Как мы это будем делать
- Возьмём
s_0
. Проверим s_0 != M
. Если равно, то решение найдено.
- Попробуем подобрать для него такое число
s_i
, что s_0 + s_i <= M
. Все варианты i
для которых s_0 + s_i > M
рассматривать не будет. В силу того, что объекты отсортированы, нам необходимо лишь перебрать их в порядке следования.
- Если
s_0 + s_i = M
, то решение найдено. Если нет, то продолжаем поиск.
- Т.е. выберем для
s_i
такое s_j (j >= i)
, что s_0 + s_i + s_j <= M
(аналогично пункту 2).
На некотором шаге может оказаться, что s_0 + s_i + s_{i+1} >= M
. В таком случае дальше осуществлять перебор не имеет смысла. Это справедливо, поскольку всё элементы отсортированы.
Необходимо вернуться на предыдущий шаг и найти s_k (k > j)
. Т.е. подобрать s_0 + s_i + s_k <= M
. Если мы перебрали все возможные варианты, но не нашли сумму такую, что она равна M
, то решения нет.
Для большего понимания, как следует организовать перебор, приведу псевдокод:
def dfs(s, sum):
for number in get_next_number(s):
new_sum = sum + number
answ = False
if new_sum == m: # Если нашли решение, то выходим из перебора
return True
elif new_sum < m: # Если решение не нашли, то пытаемся взять следующее число и повторить итерацию
answ = dfs(number, new_sum)
if answ:
return True
return False # Если ни в одном случае не удалось подобрать сумму, то выходим
dfs
нужно запустить от каждого из имеющихся чисел s
.
Точно сложность не могу оценить, но дам верхнюю оценку. Она точно не больше O(N^3)
по времени. Но следует понимать, что это завышенная оценка. Скорее всего, реальное время работы будет близко к O(N^2)
или даже O(N log N)
Я также предполагаю, что можно предложить более умное решение динамическим программированием, в частности, свести эту задачу, к задаче о рюкзаке.
Другое решение
Для этого решения достаточно каждому слову поставить в соответствие метку 1
или 0
, которая будет обозначать: нужно ли брать в ответ слово или не нужно. Таким образом, мы имеем битовую маску, состоящую из 0
и 1
. Нам необходимо перебрать все возможные комбинации (их 2^N
), посчитав для каждой из них суммарную длину выбранных слов.
Приведу пример:
один
// длина 4
два_
// длина 4
пять
// длина 4
три
// длина 3
четыре
// длина 6
Пусть M = 12
.
Маска будет состоять из 5 битов. Будем начинать перебор с маски 00000
:
10000
. Слова: один
. Суммарная длина 4 != M
01000
. Слова: два_
. Суммарная длина 4 != M
11000
. Слова: один
, два_
. Суммарная длина 8 != M
00100
. Слова: пять
. Суммарная длина 4 != M
10100
. Слова: один
, пять
. Суммарная длина 8 != M
11100
. Слова: один
, два_
, пять
. Суммарная длина 12 == M
В ответ могут войти слова:
[один
, два_
, пять
]
Спешу заметить, что вычислительная сложность алгоритма велика: O(2^N). Т.е. уже при 30 словах вы получите достаточно долго работающий алгоритм (минута или более).
Задание размеров сетки
Что касается сетки, то для задания её размеров можно задавать A
, B
-- размеры её сторон. По этим величинам вы генерируете саму сетку. A * B = M
Псевдокод
Для расположения слов, согласно вышеописанному алгоритму, можно воспользоваться "зейкой". Вы перебираете последовательно ячейки и кладёте туда по одной букве. Предварительно, разумеется, следует расположить все слова друг за другом:
words = 'одиндватричетыре'
letters_count = 0
for x in range(0, A):
if x % 2 == 0:
line = range(0, B)
else:
line = range(B, 0, -1)
for y in line:
matrix[y][x] = words[letters_count]
letters_count += 1