0

我已经成功地使用 DP 来获得问题的最佳解决方案。我面临的问题是，现在如果我想重建解决方案，我最终只能通过一种方法来获得最佳解决方案。有没有办法让我能够回溯所有可能导致最佳结果的方式/选择？

例如，如果我从具有技能 {1, 2, 2, 1} 的玩家 a、b、c、d 中选择一个团队，我可以获得最佳团队技能数为 3，并且我可以获得一种可能的方法来实现这一点{{A B C D}}。我正在寻找的是一种方法，这样我就可以获得可以公平划分团队的所有方法，团队技能计数为 3 即 {{a, c}, {b, d}} 和 {{a, b}, {c, d}}

4

2 回答 2

0

如果 X 是玩家人数。(X-1)！是可能解决方案的数量。然后，您可以使用 for 循环，将可能的解决方案作为您的长度，如果结果等于您的最佳团队技能，则将该结果存储在一个数组中。

于 2013-08-09T17:31:12.963 回答
0

DP的主要步骤是通过知道子问题的解决方案来找到问题的解决方案。这是通过找到子问题的最小（或最大值）值来完成的。有了它，您可以通过将问题与具有最小（或最大值）值的子问题连接起来来构建有向图。就像页面上的最后一张图片一样。要找到所有解决方案，只需从整个问题的解决方案中找到所有可能的路径。

于 2013-08-10T08:45:31.050 回答