Найдите лучшую комбинацию от данного набора нескольких наборов
$.urlParam = function(name) {
var results = new RegExp('[\?&]' + name + '=([^&#]*)').exec(window.location.href);
return results[1] || 0;
}
7 ответов
Мог изменить некоторые алгоритмы поиска кратчайшего пути, как Dijkstra, чтобы взвесить каждый путь стоимостью, но также и следить за ходом времени и прекратить продвигаться определенный путь, если время превышает Ваш порог. Должен найти самое дешевое, которое приводит Вас под Вашим порогом тот путь
Походит на то, что Вы имеете, назван "линейной проблемой программирования". Это также походит на проблему домашней работы, никакое преступление.
Классическое решение проблемы LP называют "Симплекс-методом". Google это.
Однако для использования того метода необходимо было сформулировать проблему правильно для описания требований.
Однако, может быть возможно перечислить все возможные пути, так как у Вас есть такой маленький набор. Такая вещь не масштабируется, все же.
Походит на задание для алгоритма Dijkstra:
Алгоритм Dijkstra, задуманный голландским программистом Edsger Dijkstra в 1959, 1, является алгоритмом поиска графика, который решает проблему кратчайшего пути единственного источника для графика с не отрицательные граничные затраты пути, производя дерево кратчайшего пути. Этот алгоритм часто используется в маршрутизации.
В статье Wikipedia существуют также детали реализации.
Если бы я знал, что только должен был иметь дело с 5 городами в предопределенном порядке, и что было только 3 маршрута между смежными городами, то я был бы скот вызвать его. Никакой смысл в том, чтобы быть изящным.
Если бы с другой стороны, это было присвоением домашней работы, и я, как предполагалось, произвел алгоритм, который мог на самом деле масштабироваться, то я, вероятно, проявил бы другой подход.
Как сказанный Baltimark, это - в основном Линейная проблема программирования. Если бы только коэффициенты для грузоотправителей (1 для включенного, 0 для не включенный) не были (двоичными) целыми числами для каждого участка, то это было бы более легко solveable. Теперь необходимо найти некоторую (двоичную) эвристику целочисленного линейного программирования (ILP), поскольку проблема является NP-трудной. Посмотрите Википедию на целочисленном линейном программировании для ссылок; на моем линейном ходе программирования мы использовали, по крайней мере, Ответвление и связали.
На самом деле теперь, когда я думаю о нем, этот особый случай solveable без фактического ILP, поскольку сумма дней не имеет значения, пока это <= 5. Теперь запустите путем выбора самого дешевого поставщика услуг для предпочтительного варианта (Conway 5:1000). Затем Вы выбираете все снова и снова самые дешевые, получающиеся 8 дней и единицы за 4 000 валют, который является слишком много, таким образом, мы прерываем это. Путем попытки других также мы видим, что они все заканчиваются дни> 5, таким образом, мы отступаем к предпочтительному варианту и пробуем второе самое дешевое (FedEx 2:3000) и затем взлеты во втором и FedEx в последнем. Это дает нам общее количество 4 дней и единиц за 9 000 валют.
Мы затем могли использовать эту стоимость для сокращения других поисков в дереве, которое будет некоторыми этапными поддеревом затратами результата, больше, на котором том мы уже нашли и отпуск что поддерево не искавший от той точки. Это только работает, пока мы можем знать, что поиск в поддереве не приведет к лучшим результатам, как мы делаем здесь, когда затраты не могут быть отрицательными.
Надеюсь, что это быстрое движение помогло немного :).
Это - задача о ранце. Веса являются днями в пути, и прибыль должна составить $5 000 - стоимость участка. Устраните все отрицательные затраты и пойдите оттуда!
Я думаю, что алгоритм Dijkstra для нахождения кратчайшего пути.
cmcculloh ищет минимальную стоимость, подвергающуюся ограничению, что он получает его там за 5 дней.
Так, просто нахождение самого быстрого пути не получит его там самый дешевый, и получение там для самого дешевого, не получит его там за необходимое количество времени.