![:-?](./images/smilies/icon_confused.gif)
Help me people! Its the dumb russian again.
I used DP for this problem.
I stored situations in structures like this:
nBank : integer; // Current bank that we re trying to save
PartolsMask : a bit vector of length M, indicating which police patrols went to the banks
At first I had one situation
nBank = 1
PatrolsMask = 00...0 // THis means that all patrols are free
From a position we can produce a new one
nBank + 1
.......1... // one zero has to be replaced by a "1"
the cost of prodution is the distance from patrol indicated by this "1" and bank number nBank.
So in my problem I start with one bit sequence, consisting of only zeros. After N steps I obtain all bit sequences with exactly N "one"s, and minimum weights counted. For every bit pattern I check every bit if it is zero. And if it is then I try to produce a new situation replacing it with a "1", and adding the weight. Every bit pattern is checked only once.
My complexity should therefore be around 20*2^20, which is close to 20 million operations. I just couldn't come up with nothing better.
Can you help me with finding a better algo? Or should I just rewrite it in C?