Dynamic Programming and Greedy Algorithms

next day → last day (22 days later) »

Orangutango

17:55

Gotta be quick

I'm at work

Parth Thakkar

sure

Orangutango

whats up?

Parth Thakkar

My friend and I were working on a problem on DP. The question was like this. There are 2 coal mines X, Y. You have 3 kinds of food packages A, B, C. Your aim is to send the packages (sequence of which is given to you) to X, Y so as to maximise the coal output.

coal output is decided like this:

for each mine, check the last 3 packages received. If they are all different, output = 3

if two are different, output = 2

else 1

e.g. if the food package sequence is ABCBCA

then you have to send the packages like this:

X: A, B, C = 1+2+3
Y: B, C, A = 1+2+3

total output = 12

(actually you could've sent all to one mine, to get the same max output)

now the doubt is:

we got this method

start from the first package (A here). See where you get the most output (X or Y) and send it there.

If both give the same output, do the same for the next package.

So, is this DP or greed?

Orangutango

Seems greedy to me.

But the problem seems like it can be solved with a greedy algorithm.

Question though: if you are given the sequence AABBCC, you would be able to split it up like X:ABC and Y:ABC, right?

Parth Thakkar

yes.

clarification: you must dispatch the food in the order of the sequence.

and it can be solved by greedy algorithm? I asked this on stackoverflow, and the fellow who answered said "it seems a simple DP program to me, i'll leave it to you"

Orangutango

18:03

I'm trying to think of a sequence were the greedy method of "give the package to the mine that will yield the highest production" fails..

You could characterize it as a dynamic program though, by defining a recursive function on the sequence of length $n$.

Parth Thakkar

how?

Orangutango

OPT(n) = max { OPT(n-1) + f(X) , OPT(n-1) + f(Y) }

Parth Thakkar

I had thought of it, but wasn't sure. Good that it works!

Orangutango

where f(z) is a function that defines how much additional production you yield by assigning the nth item of food to mine X/Y

but that still seems greedy

Parth Thakkar

but wait

Orangutango

18:05

I might be missing something.

Parth Thakkar

How is this different from greedy?

"OPT(n) = max { OPT(n-1) + f(X) , OPT(n-1) + f(Y) }"

is the same as:

Orangutango

Thats what I'm saying.

Parth Thakkar

"OPT(n) = max { f(X) , f(Y) } + OPT(n-1)"

So this isn't fully correct then.

Orangutango

I don't have time right now to try and prove whether or not a greedy solution works

Parth Thakkar

Btw, are you at least convinced that our method works? Because we couldn't really think of any counterexample and the algorithm worked on the sample input

Orangutango

18:07

I think it is

But, here is how you can know for sure:

Prove it, via exchange argument.

Parth Thakkar

exchange argument?

Orangutango

Claim your solution is optimal, and assume there is some other "optimal" solution that disagrees with your assignment at some point.

Parth Thakkar

Ok. I'll try it then.

Orangutango