matrix - Spoj backpack DP explaination -

matrix - Spoj backpack DP explaination -

i trying solve problem on spoj.i created dp solution gives me wrong answer.i creating dp matrix , taking maximum of previous reply , reply taking current good.

can explain proper solution of problem. https://www.spoj.pl/problems/backpack/

i've aced problem.

i don't know "dp solution" is, apparently problem lies in category of knapsack (still dp problem). , according problem description, it's 0/1 knapsack problem. hence equation below plenty problem, opt[i] denotes maximum value can achieved backpack total volume i.

opt[i] = max(opt[i], opt[i - items[j].vol] + items[j].value)

what makes problem special each main item have 0, 1, or 2 items attached it. have main item m, , 2 attachments a1 , a2. instead of considering m, a1, a2 separately, can imagine there 4 items bundled them:

b1, indeed m itself. hence b1.volume = m.volume , b1.value = m.volume * m.c. b2, bundled m , a1. b1.volume = m.volume + a1.volume , b1.value = m.volume * m.c + a1.volume * a1.c b3, similar b2, replace a1 a2. b4 consists of m, a1, , a2. b4.volume = m.volume + a1.volume + a2.volume , b4.value = m.volume * m.c + a1.volume * a1.c + a2.volume * a2.c

by doing operations above, can translate items bundles , can perform 0/1 knapsack using these bundles.

last not least, note bundles generated same m, 1 of b1, b2, b3, , b4 can chosen. may require little bit of hacks, shouldn't complicated. :)

matrix