1

基本上我有一个项目列表，其中包含大小和值的参数，需要以最佳方式与许多其他项目相匹配，以达到可能的最高值但保持在 maxSize 以下。

要解释该问题，请参阅以下说明。

第 1 项：尺寸 1，价值 1；

项目 2：尺寸 2，价值 4：

最大尺寸：11；最佳解决方案：1xItem1、5xItem2。

但在这种情况下，限制更高，项目更多。我的问题是找到最好的组合。到目前为止，我已经创建了一个执行此操作的算法，但由于复杂性太差，它只适用于少数项目。

我基本上在尝试所有可能的组合，这会在更多数量的项目上创建大量计算。我将路径保存为字符串（Item2->Item2->Item1->Item2...），直到总大小高于限制。如果该值高于某个其他找到的值，则将其与字符串一起保存。

我想要做的是保存所有已经完成的计算，这里是一个例子。

A -> A -> A -> A -> A

A -> B -> A -> A -> A

最后一种情况，不需要重新计算A -> A -> A，我要做的就是把它存起来。

最好的方法是什么？

目前，我的递归看起来像这样

recursion(Item item, int size, int value, String s){
  s += cust.getName() + "-";
if(value is bigger)
  bestMix = s



for(Item item : itemList){
        if(!(we break the limit){
            recursion(item, size + item.getSize(), value + item.getValue(), s);
        }
    }
}

我想要做的是在进行递归时获取已经计算的值。

为了降低时间复杂度，最简单、最聪明的方法是什么？

4

3 回答 3

2

您正在寻找的东西称为memoization ，这是一种动态编程类型的常见算法技术，可让您通过重用子问题的解决方案来提高速度。这种技术的一个必要条件是要解决的问题有一个最优的子结构，你的问题也有。

这是一种通常实现记忆的方式：您在递归例程中添加一个额外的参数，其中包含已知子问题的解决方案图。每个子问题的参数被编码为在已知解决方案的映射中查找的键。

记忆递归解决方案所做的第一件事是构造一个键并在已知解决方案的映射中运行查找。如果答案在那里，它会立即返回，而不会进一步递归。如果答案不存在，则以常规方式计算，然后在从递归调用返回之前放置在解决方案的映射中。

于 2013-10-26T14:53:15.353 回答
0

正如 dasblinkenlight 所说，记忆化是要走的路，但我决定做点别的。

我意识到我的问题与“未绑定的背包问题”相同 更多信息在这里： http ://www.cs.rit.edu/~zjb/courses/800/lec7.pdf http://en.wikipedia.org/维基/背包问题

我用动态编程解决了这个问题。 http://en.wikipedia.org/wiki/Dynamic_programming

这使我的时间复杂度好多了。

于 2013-10-27T17:36:05.070 回答
0

项目 1 的单位尺寸利润（双倍值/尺寸（为 1/1。项目 2 的单位尺寸利润更大，为 4/2。所以你应该首先用项目 2 对你的 itemList （带有Comparator）进行排序。然后是第一个遇到的解决方案可以是最大的解决方案。

另一个改进是int factor每个项目都有一个，开始尝试最高的因素。

一般来说，递归具有已完成的事情和待做的事情（候选人）的参数。

每次调用递归都会有部分结果。在访问其余部分时缓存可能是可行的，但对于已经存在的数据结构（如某些树结构）来说更有用。

于 2013-10-26T14:43:20.410 回答