Классика оптимизации: задача рюкзака (knapsack problem)

[basilisk]

Интересно, но здесь вы не сколько алгоритм рассмотрели, сколько рассказали про PuLP. Хотя интересная штучка, приму на вооружение.

А вообще, эти задачи больше известны как задачи оптимизации. И алгоритмов для их решений ой как много. Разной степени паршивости.

[Progrik]

С удовольствием почитал бы ещё таких статей, поэтому я за!

[rgaliull]

Да, надо обязательно.
Название я бы предложил более общее. Что-то связанное с математикой. Типа прикладная математика.

[hr0nix]

Именно эти известны как задачи комбинаторной оптимизации.

[hr0nix]

Рассказали бы про псевдополиномиальный алгоритм решения на основе ДП.

[belonesox]

Все это общеизвестно. Чуть менее тривиален переход от псевдополиномиальных рюкзаков к FPTAS-приближенным алгоритмам.
Все это есть и в книгах и в лекциях.

[hr0nix]

Я то знаю, что есть. А статью бы это сделало интереснее.

[megalol]

Для задач с числом вариантов менее миллиарда быстрее написать полный перебор. Это тот род задач, который пишется дольше, чем считается.

[0leGG]

Кхххм… Если число предметов не предполагается целым, то берём предмет с лучшим соотношением цена/вес и забиваем им весь рюкзак. Симплекс-методом и не пахнет.

[Andrey_Rogovsky]

Мне больше нравится про грузовики и развоз пищевых продуктов разного срока хранения, с учетом изменения их веса во время транспортировки.

[sergpenza]

Да, это не балалайками барыжить :)
Расскажите, интересно почитать

[mekegi]

а что тут рассказывать
берете n видов товара с такими параметрами как:
-стоимость за кг (или за шт)
-срок хранения
-скорость «уменьшения»(«увеличения») массы (продукт сохнет теряя в массе — либо наоборот впитывает влагу из воздуха)
-максимальная скорость транспортировки (типа хрупкие продукты — сильно трясти нельзя)

потом берете на карте m точек — складов — у каждого склада есть список товаров и их количество.
Еще берем k магазинов — которым нужно поставить товар (список товаров на каждый магазин — и количество)
и последнее автопарк — L машин с такими параметрами как грузоподъемность и максимальная скорость (ну и расход топлива можно добавить)

И теперь когда нам даны куча входных данных — необходимо построить оптимальный маршрут по времени(или стоимости) развозки товара

[DjOnline]

Да, логисты это волшебники, каждый день такое считают.

[bad1]

offtopic: к вопросам о «профессиональной деформации», прочитав заголовок «классика оптимизации» долго не мог понять, какое отношение балалайки и программа COIN-OR может помочь в продвижении сайта :))

[edelweard]

Я бы поменял блог: не в Алгоритмы, а в Python это нужно. Потому что алгоритм вы здесь не рассматриваете, а предлагаете библиотеку и её использование на Python. Это не хорошо и не плохо, просто тема другая.

[Nashev]

угу, точно. И тег типа «библиотеки» или API добавить…

[xonix]

пролог

:- 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.


[kost_bebix]

#-*- coding: cp1251 -*-

руки мыли-то хоть после такого?

[spanarin]

Как лучше было написать?

[kost_bebix]

В кодировке utf-8, очевидно же.

[guzanof]

Как-то уныло. Алгоритм толком не описан.

[SAKrisT]

сорри, а на С++ имеется решение?

[TravisBickle]

Остапу Бендеру так не хватало компьютера с этой программой…