java - 保存已计算的值

Question

基本上，我有一个项目列表，其中包含大小和值的参数，需要以最佳方式与许多其他项目相匹配，以达到可能的最高值，但保持在 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);
        }
    }
}

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

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

Answer 1

您要查找的内容名为 memoization ， dynamic programming 的常见算法技术种类繁多，可让您通过重复使用子问题的解决方案来提高速度。这项技术的必要条件是要解决的问题有 optimal substructure ，这是你的问题所在。

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

内存递归解决方案所做的第一件事是构造一个键并在已知解决方案的映射中运行查找。如果答案存在，则立即返回，而不再进一步递归。如果答案不存在，则以常规方式计算，然后将其放入解图中，然后从递归调用返回。