Algorthim to find best possible coordinate to place an item [closed]

Question

I am working on a problem but can not quite categorize it.

The problem consist of putting some items on a grid.

Each edge between an item and another item gives a certain benefit and is supposed to be placed such that I get the maximum possible sum of benefits for the particular configuration of that grid.

The grid itself has some coordinates that can not contain an item.(such as a wall)

It is also allowed not to place some items.

Can I get some guidance on how to go about it?

Algorithm, process of going about the problem, data structure to use or any relevant information.

Unfortunately I can't make the question any clearer.

Thanks

Answer 1

Here are my high-level thoughts on this.

So, this is sounding to me like a graph problem. Each item in your "item bank" will become a node in the graph. You then make edges between the nodes, and then assign a weight (integer value) to an edge based on how beneficial the relationship is between the two nodes the edge connects.

Once you've set up the graph, you could then implement a maximum flow algorithm. Of course, this would also require that you set up "source" and "sink" nodes. The maximum flow you get would then represent the maximum benefit.