Поскажите задачку, не соображу

← →
"Добрый Сок" (2013-06-04 16:22) [0]

Есть массив записей
TSubj = record F: integer; S: integer; end; A: array of TSubj;

случайным образом его заполнили
var i: integer; Cnt: integer; FOR_CNT, FOR_FIRST, FOR_SECOND: integer; begin randomize; FOR_CNT := 10; FOR_FIRST := 10; FOR_SECOND := 10; Cnt := 5 + Random(FOR_CNT); SetLength(A, Cnt); for i := 0 to Cnt - 1 do begin A[i].F := 1 + Random(FOR_FIRST); A[i].S := 1 + Random(FOR_SECOND); end;

задача
выбрать A[i] так, что бы сумма A[i].F была максимальной, но не больше заданной(Z1), при этом сумма A[i].S должна быть не больше заданной (Z2).

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

Примерно, то же самое. Вроде бы..
Разобрал, применил.

Но
тут я не могу брать второй параметр максимально до безобразия.
т.е. могу выбрать A[i] так, что бы сумма A[i].F была максимальной, но не больше заданной1, однако, при этом максимальная сумма по A[i].S, превышает заданную.
И я не могу начать откидывать элементы, потому что тогда нет гарантии, что отброшенный элемент нельзя заменить из ранее не взятого.

Есть мысли?
т.е. в той задаче чем больше, тем лучше. Тут тоже. Но есть ограничение.

← →
"Добрый Сок" (2013-06-04 16:36) [1]

> т.е. в той задаче чем больше, тем лучше. Тут тоже. Но есть
> ограничение.

не тоже, а просто - есть ограничение

← →
"Добрый Сок" (2013-06-04 16:40) [2]

а временами кажется, что это вообще не аналог той задачи.
тогда есть мысли:
1. может, перебор по всем сочетаниям - проще будет.. Если бы не так много их было.
2. или вообще, БД прикрутить..

← →
Труп Васи Доброго © (2013-06-04 16:40) [3]

Нет решения, поскольку либо одно ограничение лишнее, либо надо вводить дополнительный приоритет MAXS/MAXF.
Для примера - если нет приоритета одного условия над другим, то придём к тупику. Что "лучше" S=5:F=8 или S=9:F=3, при ограничении MAXS=10, MAXF=10?
Это как сравнивать комплексные числа - бесполезно, операция сравнения не определена.

← →
Труп Васи Доброго © (2013-06-04 16:45) [4]

Это как погрузка фуры, ограниченный объём и ограниченная грузоподъёмность. И пока не скажут что предпочтительнее, забить весь объём или нагрузить по полной, ты не сможешь определиться грузить пенопластовые блоки или свинцовые чушки.

← →
antonn © (2013-06-04 16:45) [5]

> Что "лучше" S=5:F=8 или S=9:F=3, при ограничении MAXS=10,
> MAXF=10?

брать любой выбрав все варианты с подходящим условием. например первый

← →
"Добрый Сок" (2013-06-04 16:54) [6]

>> если нет приоритета одного условия над другим,
есть. F(ist) важнее S(econd)

т.е.

> Это как погрузка фуры, ограниченный объём и ограниченная
> грузоподъёмность.

Важнее погрузить как можно больше веса. При этом, что бы проехало под аркой.

← →
Труп Васи Доброго © (2013-06-04 16:57) [7]

> есть. F(ist) важнее S(econd)

В сабже этого не было.
Тогда вообще никаких проблем в решении - жадные алгоритмы тебе в помощь.

← →
MBo © (2013-06-04 17:36) [8]

сколько записей в массиве может быть и какие ограничения на z1, z2?

← →
TUser © (2013-06-04 17:40) [9]

Очевидно, что подстановка Z1=Z1=+inf сводит задачу к дискретной задаче о рюкзаке, которая решается только перебором или эвристиками. Следовательно, в таком общем виде задача решается тоже либо перебором, либо эвристиками. У тебя максимальный перебор, какой только может быть, - 2^15, что на современном компьютере решается быстро.

Из эвристик можно попробовать метод Монте-Карло.

← →
O'ShinW © (2013-06-04 20:52) [10]

> сколько записей в массиве может быть и какие ограничения
> на z1, z2?

примерно, 100 записей. Может, чуть больше/меньше
z1, z2 - примерно такие, что половина должна отобраться, если прикинуть на глаз

> можно попробовать метод Монте-Карло.

??!
Пока не понял, как он тут поможет

> жадные алгоритмы тебе в помощь.

они не гарантируют оптимальный выбор.

← →
TUser © (2013-06-04 21:20) [11]

они не гарантируют оптимальный выбор.

Про размере 100 помогут только эвристики, а они все не гарантируют оптимальный выбор.

Монте-Карло. У тебя есть функция - сумма, которую надо максимизировать, в пространстве, размерность которого есть размерность массива. И по два возможных значения на ось (берем/не берем). При этом некоторые области этого пространства запрещены (превышено Z1 или Z2).
Выбираем начальные точки (случайно) и начинаем гулять вокруг каждой из них, случайно меняя значения параметров. При этом, в большинстве случаев, изменение одного параметра из многих не сильно меняет значение функции. Соответственно, мы получаем дерево из цепочек изменений, типа
001010010...->001010110...000010110...->...
На каждом шаге значение ц.ф. либо растет, либо падает. В зависимости от этого, мы либо продолжаем цепочку, либо нет (с определенной вероятностью, опыт показывает, что если падает, это не должно означать обязательного прекращения цепочки).
Обычно вводят не один тип шагов, а много - маленькие (например, меняется один параметр, их будет больше всего), побольше (например, меняется 5 параметров) и т.д. Ну в пределе, самый большой шаг - это новая начальная точка со своими деревьями-цепочками.
При этом обычно вводят эвристики, типа если цепочка показывает значения сильно хуже, чем многие другие, то она прекращается.

Дальше - уже только искусство, подбор параметров под конкретную задачу. А именно
1. Сколько брать начальных точек
2. Какие должны быть "классы шагов", сколько должно быть шагов разных классов
3. Как зависит вероятность продолжения цепочки от значения функции
и т.д.

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

← →
MBo © (2013-06-04 21:46) [12]

>z1, z2 - примерно такие, что половина должна отобраться
численное значение тоже важно

← →
O'ShinW © (2013-06-04 21:50) [13]

> MBo © (04.06.13 21:46) [12]

до 500, хотя бы
Ты матрицу Length(A) x Z1 собрался строить?

ps
Я что подумал- а может все-таки БД..
загнать в таблицу, сочинить запрос(подомать надо) - и пусть движок думает.
Точно, надо завтра попробовать..

← →
O'ShinW © (2013-06-04 22:02) [14]

Что самое главное - опять разово надо. Раза два - три оценить несколько наборов.

← →
O'ShinW © (2013-06-04 22:07) [15]

> TUser © (04.06.13 21:20) [11]
> тут многое уже зависит от нашего понимания задачи.

да в том и дело - что я не понимаю задачу :)
Это - прототип, который мы вывели совместно со "старшими товарищами"
и, сделав который, по словам "старших товарищей", им дальше будет проще решать их задачу.
В которой я ничего не понял, как сказал

Но это же не мешает решить абстрактно. Хотя бы за их уважение к моей скромной персоне и шайтан-машинам, на кои они косятся с подозрением :)

← →
TUser © (2013-06-04 22:14) [16]

Что самое главное - опять разово надо.

Поищи по словам "integer programming in R" - наверняка есть какая-нибудь готовая библиотека.

← →
Труп Васи Доброго © (2013-06-05 10:38) [17]

> они не гарантируют оптимальный выбор.

А где в задании про оптимальность сказано? Приоритет по F, а S должно быть лишь не больше MAXS. Ты как-то по ходу темы задание усложняешь/меняешь. Она у тебя уже приближается к классической задаче "как и рыбку съесть и на ... сесть и костями не подавиться" :) Потом не окажется, что все объекты должны быть ещё и одного цвета?
Для оптимальности надо разбить задачу на две части.
1) выявить все возможные комбинации в которых сумма Fi<=MAXF.
2) выбрать из них максимальные.
3) если таких комбинаций >1, то из них выбрать ту, где сумма Si<=MAXS
Готово.

← →
картман © (2013-06-05 10:55) [18]

> Труп Васи Доброго © (05.06.13 10:38) [17]

> 1) выявить все возможные комбинации в которых сумма Fi<=MAXF.

интересно, сколько комбинаций придется проверить для ста чисел?

← →
TUser © (2013-06-05 11:30) [19]

загнать в таблицу, сочинить запрос(подомать надо) - и пусть движок думает

Я мало понимаю в БД, но ни разу не слышал, чтобы алгоритмическая задача эффективно решалась таким способом. Он же, наверняка, займется перебором.

Целочисленное программирование - область, довольно неплохо изученная (не мной, так что конкретных советов не дам), полагаю, что есть какие-нибудь эффективные библиотеки, например, в R.

← →
"Добрый Сок" (2013-06-05 11:32) [20]

> А где в задании про оптимальность сказано?

> Ты как-то по ходу темы задание усложняешь/меняешь.

Отнюдь нет. Равно как и предыдущее замечание.

Труп Васи Доброго © (04.06.13 16:57) [7]
> есть. F(ist) важнее S(econd)
В сабже этого не было.

в [0]

> задача
> выбрать A[i] так, что бы сумма A[i].F была максимальной,
> но не больше заданной(Z1), при этом сумма A[i].S должна
> быть не больше заданной (Z2).

Где тут противоречие с дальнейшими уточнениями?
(вчера лень было спорить, но сегодня могу :) )

>> выбрать A[i] так, что бы сумма A[i].F была максимальной,
Это подразумевает, что надо сначала(приоритет) выбрать по F.
Причем выбрать максимум, что жадные алгоритмы не гарантируют

>> Приоритет по F, а S должно быть лишь не больше MAXS
нет.

из того же [0]
>> сумма A[i].F была максимальной, но не больше заданной(Z1)
>> при этом сумма A[i].S должна быть не больше заданной (Z2).

← →
"Добрый Сок" (2013-06-05 11:35) [21]

> ни разу не слышал, чтобы алгоритмическая задача эффективно
> решалась таким способом. Он же, наверняка, займется перебором.
>

не исключено. И даже, скорее всего

← →
Труп Васи Доброго © (2013-06-05 11:41) [22]

> интересно, сколько комбинаций придется проверить для ста
> чисел?

Да сколько бы ни было, а делать надо. Любой, даже самый совершенный алгоритм, можно "опустить" взяв большое количество операций. Тем более, что тут важно не просто количество чисел, а количество разных чисел. И задача получается рекурсивная. Берём число F1 из набора [F1..Fn] и получаем задачу найти все комбинации из набора [F2..Fn], сумма которых <= (MAXF-F1), и т.д.

> Это подразумевает, что надо сначала(приоритет) выбрать по
> F.

Так я и говорю, что максимальность Sum(Fi) указана, а вот максимальность по Sum(Si) нигде в задании не фигурирует. Есть лишь ограничение сверху Sum(Si)<MAXS, но никак не оптимальность. То есть в задании нет условия (MAXS-Sum(Si))=min.
Так что оптимальность была "притащена" уже потом.

← →
"Добрый Сок" (2013-06-05 12:10) [24]

> оптимальность была "притащена" уже потом.

дык, она -максимальность по Sum(Si) - вообще не была внесена.

> Есть лишь ограничение сверху Sum(Si)<MAXS

именно. Где написано про максимум по S?

> оптимальность была "притащена" уже потом

И применимо к F. И тогда, когда речь зашла про жадный алгоритм.
потому что они и по F не гарантируют оптимальности

> они и по F не гарантируют оптимальности

Why not?
Ты можешь предложить какой то другой критерий кроме "жадности", при наборе определённой суммы? Изволь изложить.
Жадная рекурсия всегда приведёт к оптимальному результату, разве нет?
Каждый раз, выбрав наибольшее число жадный алгоритм получает аналогичную задачу, только исходная сумма уменьшается на уже собранную сумму. Если на каком-то шаге необходимая сумма окажется несобираемой, то надо лишь отступить назад и взять следующее по величине число.
Если не применять критерий "жадности", то что? Простой перебор?

← →
"Добрый Сок" (2013-06-05 13:36) [26]

http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5#.D0.96.D0.B0.D0.B4.D0.BD.D1.8B.D0.B9_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1. 82.D0.BC

← →
"Добрый Сок" (2013-06-05 13:48) [27]

К точным алгоритмам относятся следующие:
Полный перебор
Метод ветвей и границ
Применение динамического программирования

Вот динамическое я и применил.. Но есть небольшая разница.
Там собирают вещи, максимально ценные, что бы забить рюкзак по фиксированной массе.

Цена - это у меня S, масса - F
я легко нахожу набор, который в сумме не превышает MaxF, но и стремится быть максимальным по S.
// что мне не надо и за что ты меня критиковал :). Но таков тот алгоритм.
Естественно, по S часто превышается MaxS, т.к. стремится быть таковым, исходя из того алгоритма.

Вот и вопрос - Что же сделать, что бы было не так
или в том алгоритме, или в другое рассмотреть можно

а то опять те самые времена наступили, походу -
>> временами кажется, что это вообще не аналог той задачи.

не осилил :(
что-то мозх закостенел

Сделал два варианта

Жадный, быстро и без гарантии.
И полный перебор.. На маленьких наборах приемлемо.

Пусть выбирают как в конкретной ситуации надо.

С бд, правда, не попробовал еще.

ЗЫ
Не ругайтесь, пожалуйста.
куки на этом компе убъю.
O"ShinW © и ДобрыйСок всем желают не болеть :)

> Жадный, быстро и без гарантии.

Я в таких случаях всегда говорю: "Ну если ТЫ так долго это делал, то кто сможет это проверить?" :)
Так что не говори заказчику про "без гарантии" и у тебя всегда будет зарплата за улучшение.

>> если ТЫ так долго это делал, то кто сможет это проверить?
Да не долго в общем-то
долго собирался с мыслями и теориями :)

> не говори заказчику про "без гарантии" и у тебя всегда будет
> зарплата за улучшение

Не , не в этом случае.
Эта работа за спасибо :)

Поскажите задачку, не соображу Найти похожие ветки