Data-structure to "map" collections to states in a dynamic-programming algorithm

I am coding for fun an algorithm to determine the best order of constructing N Building objects. Of course, each Building has its own characteristics (such as a cost, a production, a time of construction, ...). There also exists a total ordering over the Building objects based on those characteristics.

At some point in my dynamic programming I need an adapted data structure to retrieve the best result reached so far to construct k (k<=N) Building. I need this data structure to somehow "map" a collection of the k Building (possibly sorted, since constructing Building b1 and then b2 or b2 and then b1 leaves me with the same N-k buildings but can most likely lead to different states) to the "best-state" reach so far.

I could probably use simple HashMap but it implies repeating a huge number of times collections containing the same elements, not taking into account that [b1,b2] is 开发者_Python百科a sub-collection of [b1,b2,b3,b4] for instance.

I hope I made myself sufficiently clear on that one and I thank you for your help :)

---

It's impossible to answer without knowing the structure of your solutions.

But, if the solution for k is obtainable from the solution of (k-1) by inserting a building b into position j, then you can have simply an hashmap mapping integer i to the "delta" between the solution for i and the solution for i-1, expressed by a couple.

But having to deal explicitly with deltas can be hideous, because you need to do traversing to get a solution. You can solve this by let the delta know the referenced deltas (i.e., passing the delta for (k-1) in the constructor of the delta for k), and then exposing a method getSolution() which performs the actual traversing.

You can extend this idea to similar solution structures.

---

You can use a LinkedHashSet for the key and the value is the cost of building the Buildings contained in the set in its iteration order. It's a bit of a hack but according hashCode and equals it should work. It you prefer to be more explicit go with the hashmap of set to pair of cost and build order.

---

If your solutions look like ABC,cost1, ABCD,cost2, create a linked list d-> c-> b-> a. Store solutions as tuples of cost and a reference to the last element contained in your Solution (the earliest in the list)