迭代和遞歸解決方案

時間複雜度我試圖解決以下問題：迭代和遞歸解決方案

我覺得我已經給了它很多的想法和嘗試了很多東西。我設法解決它，併產生正確的價值，但問題是它不夠高效。由於時間限制超過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

迭代和遞歸解決方案

回答

相關問題