Sane

lectric, that sounds like a very good greedy algorithm, but coding all of those heuristics also sounds very difficult and time consuming. I wager it would be harder to code than a linear solution. But all right, I've said enough. Time for me to get back to my work.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Liglogthepanda

Thanks to everyone who's replied thus far (you're bloody good). My colleague and I in this project will have a look during the week in our spare time and report back!

This is actually part of a module for a charity with a youth programme which we volunteer at. To get various awards, you see, they need to do subjects in various areas, and some subjects can be counted in multiple areas. Whoever dreamt it up clearly decided that amateur programmers needed a challenge *shrug*.

Sane

Since you sent me a message saying you might look into this, I might as well reply with a great resource for solving this problem.

There is a tutorial from the USA's Computing Olympiad training pages that you can only see if you're doing their training, but I've found a blog where someone's snipped it out and posted it publicly.

It has the full pseudo-code for finding the max-flow a graph. It's 43 lines, so it's not bad at all. But in all honesty, if you've never done anything with building a graph, writing an adjacency list data structure might just be downright frustrating for you.

http://hi.baidu.com/xhljj/blog/item/...bb48f3144.html

Otherwise, the code's pretty much all there. Then you'd have to add some code to increase the upper-bound on the edges if there are any items that can't be distributed.

Take a look at it for fun, or for intrigue. Then when you realize it might not be worth your time for a task given to volunteer programmers, it should be less frustrating to go with a greedy approach like Jabo and lectric suggest.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Liglogthepanda

Yes, but frustrating we can cope with, so long as it's interesting! There's no real urgency on it, so we can aim high ("ambitious but rubbish"?)

You know, I had a hunch a good idea was going to be something like this. Back at A-level, I read a textbook on decision maths, which briefly mentioned something like this. How on earth you found that resource I don't know, but it'll make good bedtime reading.

The greedy algorithm as previously mentioned is something that we were considering before (it's the way we'd do it by hand), but programming it seems really tough as it's quite tricky to pin down.

Liglogthepanda

Right, so after some discussion we'd like to use Sane's graph theory solution - it sounds fun!

I've looked around and I reckon I understand it now. What I'm struggling with at the moment is that Dijkstra's is a shortest path alg'm (there are lots of examples of this on the web). But I don't know how we'd adapt it to find max-flow (aka max-match). Lots of stuff on the web we've found says that it can be adapted for max-flow problems, but then either gives you no method for doing this, or shows you how to get the numeric value of the max-flow, neither of which I think is of much use to us. I can't find any applets on Google of this max-flow alg'm in use. So how do we adapt Dijkstra's? There's only so much tea left in England for us to brew our thoughts over!