Comments 24
Интересно, но здесь вы не сколько алгоритм рассмотрели, сколько рассказали про PuLP. Хотя интересная штучка, приму на вооружение.
А вообще, эти задачи больше известны как задачи оптимизации. И алгоритмов для их решений ой как много. Разной степени паршивости.
А вообще, эти задачи больше известны как задачи оптимизации. И алгоритмов для их решений ой как много. Разной степени паршивости.
Рассказали бы про псевдополиномиальный алгоритм решения на основе ДП.
Для задач с числом вариантов менее миллиарда быстрее написать полный перебор. Это тот род задач, который пишется дольше, чем считается.
Кхххм… Если число предметов не предполагается целым, то берём предмет с лучшим соотношением цена/вес и забиваем им весь рюкзак. Симплекс-методом и не пахнет.
Мне больше нравится про грузовики и развоз пищевых продуктов разного срока хранения, с учетом изменения их веса во время транспортировки.
Да, это не балалайками барыжить :)
Расскажите, интересно почитать
Расскажите, интересно почитать
а что тут рассказывать
берете n видов товара с такими параметрами как:
-стоимость за кг (или за шт)
-срок хранения
-скорость «уменьшения»(«увеличения») массы (продукт сохнет теряя в массе — либо наоборот впитывает влагу из воздуха)
-максимальная скорость транспортировки (типа хрупкие продукты — сильно трясти нельзя)
потом берете на карте m точек — складов — у каждого склада есть список товаров и их количество.
Еще берем k магазинов — которым нужно поставить товар (список товаров на каждый магазин — и количество)
и последнее автопарк — L машин с такими параметрами как грузоподъемность и максимальная скорость (ну и расход топлива можно добавить)
И теперь когда нам даны куча входных данных — необходимо построить оптимальный маршрут по времени(или стоимости) развозки товара
берете n видов товара с такими параметрами как:
-стоимость за кг (или за шт)
-срок хранения
-скорость «уменьшения»(«увеличения») массы (продукт сохнет теряя в массе — либо наоборот впитывает влагу из воздуха)
-максимальная скорость транспортировки (типа хрупкие продукты — сильно трясти нельзя)
потом берете на карте m точек — складов — у каждого склада есть список товаров и их количество.
Еще берем k магазинов — которым нужно поставить товар (список товаров на каждый магазин — и количество)
и последнее автопарк — L машин с такими параметрами как грузоподъемность и максимальная скорость (ну и расход топлива можно добавить)
И теперь когда нам даны куча входных данных — необходимо построить оптимальный маршрут по времени(или стоимости) развозки товара
offtopic: к вопросам о «профессиональной деформации», прочитав заголовок «классика оптимизации» долго не мог понять, какое отношение балалайки и программа COIN-OR может помочь в продвижении сайта :))
Я бы поменял блог: не в Алгоритмы, а в Python это нужно. Потому что алгоритм вы здесь не рассматриваете, а предлагаете библиотеку и её использование на Python. Это не хорошо и не плохо, просто тема другая.
пролог
:- use_module(library(clpfd)).
solve1(Vars, Res) :-
Vars = [X1, X2, X3], Vars ins 0..10,
3*X1 + 5*X2 + 12*X3 #=< 40,
F = 17*X1 + 30*X2 + 75*X3,
once(labeling([max(F)], Vars)),
Res is F.
?- solve1(Vars, Res).
Vars = [2, 2, 2],
Res = 244.
#-*- coding: cp1251 -*-
руки мыли-то хоть после такого?
руки мыли-то хоть после такого?
Как-то уныло. Алгоритм толком не описан.
сорри, а на С++ имеется решение?
Остапу Бендеру так не хватало компьютера с этой программой…
Sign up to leave a comment.
Классика оптимизации: задача рюкзака (knapsack problem)