以动态编程算法将集合“映射”到状态的数据结构

我正在编写有趣的算法编码，以确定构建N个建筑物对象的最佳顺序。当然，每座建筑都有自己的特点（如成本，生产，施工时间......）。基于这些特征，还存在对Building对象的全部排序。以动态编程算法将集合“映射”到状态的数据结构

在我的动态规划中的某个时刻，我需要一个适应的数据结构来检索到目前为止构建k（k < = N）Building所达到的最佳结果。我需要这个数据结构以某种方式“映射”k建筑物的集合（可能排序，因为构建建筑物b1，然后是b2或b2，然后b1使我具有相同的Nk建筑物，但最有可能导致不同的状态）到“最佳状态”到目前为止。

我大概可以使用简单的HashMap，但它意味着重复包含相同元素的大量集合，而不考虑[b1，b2]是[b1，b2，b3，b4]的子集合，例如。

我希望我自己做的，一个足够清楚的，我感谢你的帮助:)

来源

2011-05-28 Jean Logeart

不是100％明确的问题，但可能有一个类BuildingSet可能有用，它可以包含Building和BuildingSet的对象？然后你可以让BuildingSet x = [b1，b2]和BuildingSet y = [x，b3，b4]。 – Cephron 2011-05-28 15:18:57

这是不可能不知道您的解决方案的结构来回答。

但是，如果可以通过将建筑物b插入位置j从（k-1）的解中获得k的解，那么可以简单地将整数i映射到解决方案之间的“delta”我和i-1的解决方案，由一对夫妇表达。

但是必须明确处理deltas可能会很糟糕，因为您需要遍历才能获得解决方案。你可以通过让增量知道引用的增量（即，在k的增量的构造函数中传递（k-1）的增量），然后暴露执行实际遍历的方法getSolution()来解决这个问题。

您可以将此想法扩展到类似的解决方案结构。

来源

2011-05-28 15:20:33 akappa

您可以使用LinkedHashSet作为键值，该值是以迭代顺序构建集合中包含的Buildings的成本。这有点破解，但根据hashCode和等于它应该工作。你更喜欢更明确地使用设置成对的成本和构建顺序的hashmap。

来源

2011-05-28 15:49:15 karmakaze

如果您的解决方案看起来像ABC，cost1，ABCD，cost2，则创建链接列表d-> c-> b-> a。将解决方案存储为成本元组以及对解决方案中包含的最后一个元素（列表中最早的元素）的引用

来源

2011-05-29 06:27:43 Nicolas78

以动态编程算法将集合“映射”到状态的数据结构

回答

相关问题