Задача о рюкзаке, используя 1-D массив?

Question

[floppa322]

Почему, когда традиционно рассказывают про рюкзак (однопараметровый, где у предметов есть только вес: N предметов с весами wi и max размер рюкзака S), то используют двумерный массив состояний, где dp[i][j] = bool, который означает, можно ли набрать вес j используя или не используя i-й предмет. Но ведь это решение тратит N * S памяти, можно же сделать то же самое с одномерным массивом dp[i] = true, проходя по всем true и дорисовывая ребра из i-го веса (если там true) в dp[i + wj] = true. По времени тоже N * S, но по памяти просто S

Comments

[#]

любопытно.. а вы таки реализовали свою версию?
реально сравнили время и память?
если на с-подобном языке, буду благодарен за пример реализации ))

[floppa322]

dp[0..S] <----- false
dp[0] = true
for each item in items
for i: 0..S
if (dp[i] && (i + item.weight <= S)) then dp[i + item.weight] = true

написал псевдокодом )

[#]

floppa322, ок, покурю )))
если дойдут руки сравнить с типовыми реализациями - отпишусь )))

[floppa322]

pfg21, то есть это чисто в академических целях делается, никаких преимуществ 2-D не даёт ?

[pfg21]

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

Answer 1

[Wataru]

Вы не правы. Двумерный массив считает, можно ли набрать вес i используя первые j предметов. А не j-ый предмет.
Далее, обычно можно сэкономить память храня и пересчитывая только одну строку этого массива, но ДП все еще остается двумерным. Также числа Фибоначчи можно считать храня лишь 2 последних числа, но на самом деле там массив на n элементов в дп.

Этот трюк не всегда возможен. Например, если вам надо не только максимальный вес/цену найти, а еще и набор предметов. Восстановление ответа не всегда можно сделать лишь по последней строке.

Comments

[floppa322]

Двумерный массив считает, можно ли набрать вес i используя первые j предметов. А не j-ый предмет.

я на самом деле это и имел в виду, просто коряво написал )

[floppa322]

для одномерного массива вроде всё ок восстанавливается
d[i] = bool хранится, можно ли получить вес = i
ну и для восстановления ответа, находясь на j-м предмете, в позиции i проверяем, есть ли ребро (dp[i - item[j].weight] == true) используя j-й предмет, если есть то добавляем в ответ, и идём к j-1 предмету

[Wataru]

floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ. В некоторых задачах, как рюкзак без цен с повторениями, действительно, трюк с сокращением таблицы ДП не имеет недостатков.

[floppa322]

floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ

хм, а если в таком случае для i-го веса перебирать все N предметов ? тогда правда в отличие от 2-D динамики сложность восстановления ответа будет не S, а N * S

[Wataru]

floppa322,

хм, а если в таком случае для i-го веса перебирать все N предметов ?

Не поможет. Проблема в том, что вы не знаете, какие из предметов можно брать для текущего i-ого веса - вдруг они вам очень нужны в конце будут. И просто по одной последней строке вы никак это не определите вообще. И в итоге ваше восстановление ответа может взять один предмет несколько раз, или, если этого избегать, прийти в тупик: все возможные предметы для i-ого веса уже взяты в ответ и что делать вообще непонятно.

Иногда можно прям в массиве хранить множество всех предметов, Но это уже не O(S) памяти. Возможно, это все равно меньше O(SN) для полной матрицы, но не факт.