From: Ilmari Heikkinen <ilmari.heikkinen@...>
Date: 2006-01-22T07:04:28+09:00
Subject: Re: Ruby Quiz #62

Hi,
On 1/19/06, Andrew Dudzik <adudzik@gmail.com> wrote:> I took a few shots at #62 and was unable to come up with anything that would> terminate in a reasonable amount of time. ("reasonable" = "overnight")
I guess the computational complexity of an optimal solver is n!, whichwould make solving anything bigger than 10 boxes a feat. And since binpacking problem is strongly NP-hard, checking that a solution isoptimal would take non-polynomial time as well.
A nice approach might be using neural nets / evolutionary algorithms /simulated annealing / some other funky optimization algorithm forfinding solutions that are better than what the greedy algorithmsgive, without taking years to run.

-Ilmari