langobardi
Newbie | Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору
Цитата: Вся задача сводится к поиску такой матрицы (из исходной), в которой сумма всех элементов минимальна. Для этого и нужен перебор всех возможных вариантов матриц. | seva_smr, для решения этой задачи(судя по вашим примерам), вам просто в каждой строке нужно найти минимальное число. Может быть вам нужно именно подматрицу найти с минимальной суммой чисел? Тогда задача решается динамикой, но нужно знать каковы размеры искомой подматрицы. akaGM прав, вам следовало бы сразу привести условие задачи. Добавлено: seva_smr Вашего последнего поста не успел увидеть. Цитата: Понятно, что достаточно просто смотреть минимальную цену по постам для каждой номенклатуры, тогда сумма и будет минимальна. Но в задаче есть свои различные ограничения по весу, объёму и т.д. и поэтому решено сделать перебором всех возможных вариантов растаможки. | Перебирая таким образом все возможные варианты, это не будет менее затратным ни по весу ни по объёму. Сами судите: по времени, для нахождения мин эл-та в каждой строке мы тратим O(NxM). А для полного перебора при помощи цикла O(N^M). Что касается веса, то получится примерно одно и то же, хотя нам ещё во-втором случае нужно заведомо задавать ещё один массив, а в первом достаточно и одного заданного. |