CODEWITHSUNDEEP
algorithmdata-structuresdecision-tree
Baguette
Baguette

Reputation: 27

Choosing data structure for resource allocation decision tool

I'm trying to make a small decision making tool.

I have a list of event that occur at preset moments (X always occur at 00:12 for exemple), each event is weighted

I got a list of ressources, each ressource have a duration and a timespan before being available again. Also, each ressource modify in its own way the weight of events that happen when they are active. No ressource spent is also a possibility.

As I thought my thing, tthe optimal ressource allocation is the highest sum of events weights, applying ressource modifiers if event happen during ressource active time.

I got real trouble modeling my problem in terms of data structure. I thought about two possible solutions :

I had the first intuition I should have a tree where each node represent and event (by its timer) and the state of my choice list (which are available, which aren't, which are active). But how do I track changes between nodes then ? I got trouble to see how I would manage such structure.

Is a boolean 2D-array, with each line an event, and each column a choice, then i go through the columns, and where true, get the corresponding event weight, corresponding choice weight modifier, etc... a good step toward a decent solution ?

Any insight ?

Upvotes: 0

Views: 438

Answers (1)

ERiver
ERiver

Reputation: 73

I would suggest looking into a priority queue where you sort your resources by their event weights, such that the top of the priority queue would be the resource with the highest weight. Once an item is available you can add it to the queue. Since you mention you want to reprioritze item weights I would suggest looking into a fibonacci heap to act as the underlying data structure for the priority queue.

Upvotes: 0

Related Questions