KoStYaN146, первая команда может быть одной из трех: движение, ремонт и поиск (подготовку второй раз подряд делать нельзя). После движения может быть 3 варианта: движение, подготовка, поиск. После ремонта - тоже три: подготовка, движение и поиск. После поиска - только два: движение, подготовка.
Я правильно понял, что есть ограничение, что надо пройти не меньше заданного количество вершин? При этом найти минимальный из возможных путь? Что за радиус? Т.е. надо найти минимальный путь, что не менее K клеток лежат от него на расстоянии не более r?
Как у вас препятствия на карте - стены между соседними клетками, или некоторые клетки посещать нельзя? Соседей 4 или 8 (можно ли ходить по диагонали)?
Николай, Ну дак это же будет минимизировать общее количество коробок и просто выдавать math.ceil(order/9).
Ну, в некоторых случаях оно будет одну коробку заменять на что-то меньшее (если order % 18 < 6).
При чем тут НОК? Это целевая функция такая, или вы к нему пришли исходя из целевой функции.
Логично было бы минимизировать количество коробок, а потом лишнее место. Тогда задача решается так - жадно берем самую большую коробку, деля на 9 нацело. Потом, в зависимости от остатка берем или 9, или 6, или 3.
Т.е.
box[2] = order // 9
if (order % 9 > 0)
box[(order % 9 - 1)//3] += 1
tarp20, В вопросе у вас пока написано просто "в оптимальный сопосб". И никому, кроме вас непонятно, что значит - "оптимальный". Мне, например, большие коробки нравятся, потому что мой кот любит в них сидеть - поэтому любой оптимальный заказ должен содержать большую коробку. Но это мне, а что нужно в задаче - я не знаю.
Вы в сишный код передавайте массив дуг, который можно сделать тремя массивами (начало, конец и длина отдельно). А вектор векторов уже можете строить в сишном коде.
arktang, А еще V1 не подсчитать без сечегния на границы. Там, судя по рендеру, окончание - отрезок. А какой он длины? Как он расположен? V3 - нельзя подсчитать не зная под каким углом третье сечение к остальным двум. И расстояние L3 не понятно между какими точками меряется.
И пирамидой считать V2 нельзя. Только если продление сторон сойдется в точку, ибо в формуле вывода объема участвуют подобные фигуры и гарантируется, что площадь сечения посередине - среднее арифметическое сечений в концах.
А в вашем случае сечения вообще не полигонами будут - а кривыми.
Если вам нужна get_dists, то можете взять dijkstra и вернуть массив distances после цикла while. Остальной код не нужен.
Что бы 2 раза не гонять дейкстру для расстояний и пути можно вернуть одновременно массив distances и prev. Тогда по prev кодом в Dijsktra после while можно построить путь, если он нужен.
Ваш массив graph перобразуется в Graph в функции Load.
Это фактически и есть двумерый массив, но там ребра из каждой вершины сгруппированы в одну строчку.
Adamos, Как в вашем примере отсекается оптимальный вариант? Вариант "берем только первого продавца" - не отсекается, потому что он имеет минимум по всем товарам из всех взятых продавцов (он один).
Критерий не говорит, что какого-то продавца никогда не будет смысла брать потому что другие существуют. Он говорит, что не будет смысла брать его вместе с некоторыми другими.
Вот еще раз цитата:
Очевидно, что если мы берем какое-то множество продавцов, то каждый из них должен иметь минимальную цену по какому-то товару.
Adamos, Поэтому брать всех трех продавцов - невыгодно. Если какой-то продавец не дает минимум покакому-то товару, то все покупаемые у него товары можно купить у кого-то другого дешевле. Значит можно сделать так и выкинуть этого продавца и не платить ему за доставку.
Брать только перовго продавца или только двух других - локально оптимальные решения и их оба придется рассматривать в переборе.
Это лишь критерий оптимальности, достаточный, но не необходимый. Я предложил использовать его для отсечения в переборе.
Nurdaulet Turar, Можно ли в условии ставить несколько комманд? Вроде - если текущая клетка филоетовая - повернуть направо, шаг вперед, окрасить в оранжевый, вернуться в начало.
Magneto903, Зависит от графа. Дейкстра работает всегда более или менее одинаково. Этот алгоритм может работать в несколько раз быстрее или в сотни раз медленнее.
На сях, конечно, быстрее будет в среднем. Я бы советовал дейкстру в wasm скомпилировать, если вам так скорость нужна.
Magneto903,
О, я понял, почему этот алгоритм работает.
Это что-то типа волнового алгоритма и алгоритма Белла. Всякий раз как где-то ребро релаксируется, конец снова добавляется для рассмотрения.
Проблема с ним, что он может работать сильно дольше на неудачных тестах, потому что каждая вершина может быть в очереди сколько угодно раз. Тут вам повезло с графом, но может быть сииильно хуже.
Можно вообще сделать так, что длина очереди будет O(2^n) для n вершин. Но это будут весьма искусственные тесты. Может в вашем случае оно в среднем будет работать лучше.
