迭代和递归解决方案

时间复杂度我试图解决以下问题：迭代和递归解决方案

我觉得我已经给了它很多的想法和尝试了很多东西。我设法解决它，并产生正确的价值，但问题是它不够高效。由于时间限制超过1秒，它完成了2次Kattis测试，并且3次失败。现在我想知道他们测试的输入是什么，我害怕。

我从一个递归解决方案开始，并完成了。但后来我意识到它不够高效，所以我试图改用迭代解决方案。

我开始读取输入并将其添加到ArrayList。然后我调用下面的方法以目标为1000

public static int getCorrectWeight(List<Integer> platesArr, int target) { 
    /* Creates two lists, one for storing completed values after each iteration, 
    one for storing new values during iteration. */ 
    List<Integer> vals = new ArrayList<>(); 
    List<Integer> newVals = new ArrayList<>(); 

    // Inserts 0 as a first value so that we can start the first iteration. 
    int best = 0; 
    vals.add(best); 

    for(int i=0; i < platesArr.size(); i++) { 
     for(int j=0; j < vals.size(); j++) { 
      int newVal = vals.get(j) + platesArr.get(i); 
      if (newVal <= target) { 
       newVals.add(newVal); 
       if (newVal > best) { 
        best = newVal; 
       } 
      } else if ((Math.abs(target-newVal) < Math.abs(target-best)) || (Math.abs(target-newVal) == Math.abs(target-best) && newVal > best)) { 
       best = newVal; 
      } 
     } 
     vals.addAll(newVals); 
    } 
    return best; 
}

我的问题是，有没有一些办法，我可以减少这一个大量数据的时间复杂度？

来源

2016-09-17 Viktor Plane

你应该用动态规划 – Kelvin

获得基于knacksack-问题或子集和问题的算法（动态规划，分支定界;可能与启发式相结合）的启发。这个问题很可能是np-hard，这意味着在给定一个通用算法的情况下存在一些非常困难的（不可能解决的）实例。没有关于实例的一些假设，很难引导你到一个（经验上的）。 – sascha

迭代与递归....这可以给你几个百分点的加速，也许在一些罕见的情况下更多...不值得。更好的算法可以将指数时间改变为例如二次方 - 无限的胜利。 – maaartinus

主要问题是vals和newVals的大小可以非常快速地增长，因为每次迭代可以使其大小加倍。你只需要存储1000个应该可以管理的值。您正在限制这些值，但因为它们存储在ArrayList中，所以它会以很多重复值结束。

如果您使用的是HashSet，那么它应该可以提高效率。

来源

2016-09-17 21:34:06 fgb

您只需要存储大小为2001（0至2000）的DP表格让dp[i]表示是否可以形成i公斤的权重。如果权重超出数组范围，请忽略它。例如：

dp[0] = 1;  
for (int i = 0; i < values.size(); i++){ 
    for (int j = 2000; j >= values[i]; j--){ 
     dp[j] = max(dp[j],dp[j-values[i]); 
    } 
}

这里，values是所有原始权重被存储。 dp的所有值都将设置为0，但dp[0]除外。

然后，检查1000是否有可能。如果没有，请检查999和1001等。这应该运行在O(1000n + 2000)时间，因为n最多只能运行1000次。

顺便说一下，这是一个改进的背包算法，你可能想查找一些其他变体。

来源

2016-09-18 01:10:45

如果您对这种类型的问题过于笼统，您可能会认为您必须检查所有可能的输入组合（每个重量可以包含或不包含），给您提供组合以测试您是否有n投入。然而，这并不重要。相反，这里的关键是所有权重都是整数，目标是1000.

让我们首先检查角落案例，因为这会限制搜索空间。

如果所有权重> = 1000，请选择最小值。

如果至少有一个权重为1000，那么总是比任何权重> = 2000更好，因此为了组合的目的，您可以忽略任何权重> = 1000。

然后，应用动态编程。保留一组（从其他海报中得到的HashSet，但BitSet甚至更好，因为它的最大值很小）前k个输入的所有组合，并通过将所有先前的解与k + 1组合来增加k '输入。

当您考虑所有可能性时，只需搜索位矢量以获得最佳响应。

static int count() { 
    int[] weights = new int[]{900, 500, 498, 4}; 

    // Check for corner case to limit search later 
    int min = Integer.MAX_VALUE; 
    for (int weight : weights) min = Math.min(min, weight); 
    if (min >= 1000) { 
     return min; 
    }   
    // Get all interesting combinations 
    BitSet combos = new BitSet(); 
    for (int weight : weights) { 
     if (weight < 1000) { 
      for (int t = combos.previousSetBit(2000 - weight) ; t >= 0; t = combos.previousSetBit(t-1)) { 
       combos.set(weight + t); 
      } 
      combos.set(weight); 
     } 
    } 
    // Pick best combo 
    for (int distance = 0; distance <= 1000; distance++) { 
     if (combos.get(1000 + distance)) { 
      return 1000 + distance; 
     } 
     if (combos.get(1000 - distance)) { 
      return 1000 - distance; 
     } 
    } 
    return 0; 
}

来源

2016-09-22 22:41:32 ExMathGuy

迭代和递归解决方案

回答

相关问题