PPTEST cookoff 39

general
, ,
1

can we solve the problem using one-D array.If yes how?

2

You can cut down the space usage significantly.

And the tester’s solution uses exactly that. Here’s the pseudo code.

FOR i -> 0 to W
    G[i] = 0
ENDFOR

(*)FOR i -> 1 to N
    FOR j -> W downto 0
        G[j] = max(G[j + T[i]], G[j] + C[i] × P[i])
ENDFOR

In many DP problems, you just require the past few values so you can get rid of the not-to-be-used-in-future memory, and modify your code accordingly to save space. Specially when you require just the optimal answer and NOT a solution to the problem, where you need to reconstruct the solution from the final solution by guessing as which path you took so that you got the current answer, and so on.

EDIT: Link for the editorial.

3

got it…Thanks…earlier my j loop was running from j=0 to w and this was creating problem…but after going through the editorial i got my mistake…

4

glad. Good Luck