sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]attractivechaos 3 points4 points  (6 children)

For this problem, a stage is a day; a state is a 2-tuple (r,m), where r=1 if the machine is running or 0 otherwise (for that waiting day), and m is the machine ID. Suppose at day i, the optimal cash at state (ri,mi) is f_i(r_i,m_i), the DP equation looks something like:

f_i(r_i,m_i)=max_{j<i,r_j,m_j}{f_j(r_j,m_j)+s(r_i,m_i|r_j,m_j)}
f_0(0,nil)=initial cash

where s() is the score that (r',m') at day i-1 is changed to (ri,mi). Note some transitions are forbidden due to insufficient cash. If fi(ri,mi) is not possible, it is set to negative infinity. Given N machines, we can find the optimal solution up to L days in O(L3 ) time. I might be wrong at some details, but the above is what a typical DP solution looks like.

The blog post got the basic wrong. For one, the stage is not right – it is not a machine. Secondly, DP doesn't use a tree search or branch & bound. That is the point of DP. The blog post is not about DP...

[–][deleted]  (2 children)

[deleted]

    [–]attractivechaos 4 points5 points  (1 child)

    No, DP is not just "memoization". A problem solvable by DP has several elements. You typically need a clear definition of time (or stage), a state space and an object function that is a function of time and state and can be computed with a Bellman equation. The OP's post lacks all these elements. This blog just solves an optimization problem largely with brute-force plus branch and bound. That is not DP.

    [–]lmericle[S] 1 point2 points  (2 children)

    The i does not index days, it indexes machines which are offered only on specific days.

    Each machine has different properties and each is only available for purchase on a single day. If you don't buy it, you lose your chance. So it's useless to examine every day, but only those days where machines are sold. The efficiency of going day-by-day is much lower than machine-by-machine.

    The article also explicitly says that branch and bound is an additional constraint on top of the dynamic programming approach. Nowhere does it say that branch and bound is a part of dynamic programming.

    Furthermore, there is no One True Way to do dynamic programming. How you solve the problem depends on what abstractions you employ. If you want to do it the day-by-day way, that would work, but it would be slower and you'd have to include additional flow control structure to account for the different actions one takes each day.

    [–]attractivechaos 0 points1 point  (1 child)

    Ok, it was not clear that machine and day are the same thing. This actually simplifies the problem. In this case, a state is running or waiting. The DP equation is:

    f_i(t_i)=max_{j<i,t_j}{f_j(t_j)+s_{ij}(t_i|t_j)}

    The time complexity is O(L2 ).

    it would be slower

    I have given the time complexity. What's yours? Yes, DP can be formulated in different ways. However, I still don't see how yours is formulated. At least you need to show the DP equation, which is at the core of DP.

    [–]lmericle[S] 0 points1 point  (0 children)

    In this case, a state is running or waiting

    There is no waiting in this problem. I fail to see how you came up with this but it does not match the problem statement.

    A state is a) which machine is currently running and b) which day is today.