Re^5: Bin packing problem variation repost (see[834245])

BrowserUk,
Ah, I see. I am not entirely convinced smart brute forcing is entirely out of the question. The maximum number of iterations that you could possibly have to check is 186!. If you were dynamically generating your dials, the number goes way down.

dial 1 - any of the 186 indices (say 311)
dial 2 - any of the 186 indices that isn't dial 1's current (say 296)
dial 3 - any of the 186 indices that isn't dial 1 or 2's current (say 
+257)
dial 4 - can't be anything because the sum of 1-3 is 864.
[download]

This is extremely messy to do in C though I have done it. Once you get to dial 7 you treat it as though it were dial 1 as far as sum goes. Doing it this way though cuts the possible paths down early and considerably assuming the data isn't designed for worst case.

I have no idea when I will have anything resembling free time again though so this is just an idea.

Cheers - L~R

Comment on Re^5: Bin packing problem variation repost (see[834245]) Download Code

Replies are listed 'Best First'.
Re^6: Bin packing problem variation repost (see[834245]) by BrowserUk (Patriarch) on Apr 27, 2010 at 16:48 UTC
The maximum number of iterations that you could possibly have to check is 186!. Did you miss that 186! ~= 7.667e+342? Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. RIP an inspiration; A true Folk's Guy	[reply]
Re^7: Bin packing problem variation repost (see[834245]) by Limbic~Region (Chancellor) on Apr 27, 2010 at 23:47 UTC
BrowserUk, No, I didn't miss that. I only stated it that way because I messed the math up the first time and I wanted to make sure I had it right this time. I knew you would correct me if I was wrong. I know it seems like an insurmountable number and it very well may be. I am not writing it off as effectively impossible without spending a little time setting up the self-pruning system I outlined above. I have done so in the past with seemingly impossible numbers (albeit not this large) with positive results. Unfortunately, I am more focused on real world problems (DB2 is a real PITA btw). Cheers - L~R	[reply]