- #1

- 19

- 0

http://img207.imageshack.us/img207/8952/neatoteeheesu5.jpg [Broken]

thx

thx

Last edited by a moderator:

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter nomi
- Start date

- #1

- 19

- 0

http://img207.imageshack.us/img207/8952/neatoteeheesu5.jpg [Broken]

thx

thx

Last edited by a moderator:

- #2

- 441

- 0

And How can you pick 15 squares from a 12x12 array so that no two selected squares are in the same row or column?

- #3

- 19

- 0

thats what i dont understand

- #4

- 441

- 0

Please clarify with your teacher/professor, and let us know.

- #5

- 441

- 0

Have you ever heard of the travelling salesman problem? As wikipedia states

Given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?

One method of solving this problem (again according to wikipedia) is:

Constructive heuristics

The nearest neighbour (NN) algorithm (the so-called the greedy algorithm is similar, but slightly different) lets the salesman start from any one city and choose the nearest city not visited yet to be his next visit. This algorithm quickly yields an effectively short route.

Do you see how you can apply this to your problem?

Hint: think of column one as a city, and all the rows in column one as different routes to the next column. Of course here you want to maximize, not minimize, but the general principal is the same.

- #6

- 737

- 0

Then, you may want to look up what Diffy posted or consider better mathematical and algorithmic approaches to the problem.

- #7

- 19

- 0

thanks guys

- #8

- 355

- 3

Use the Hungarian Algorithm. (It's an algorithm designed specifically for that problem)

- #9

uart

Science Advisor

- 2,797

- 21

The minimum, seems to be 143 by picking 7, 18, 24, 5, 11, 9, 11, 14, 6, 5, 21, 12 in each row respectively. You should be able to find the maximum just as easily.

Just wondering what CPU that was run on Tedjn?

BTW. I'm also a fan of brute force when you can get away with it, it must be the Engineer in me :). My exhaustive search ran in under 30 sec written/compiled in Borland Delphi 7 (pascal) and run on an Athlon64-3800+. I got the same answer as you when I set it to find a minimum. The actual problem here is to find a maximum however but of course that's a trivial program change. I wont post the solution since I think the OP is still working on it.

Last edited:

- #10

- 737

- 0

- #11

uart

Science Advisor

- 2,797

- 21

Share: