給定一個列表和一個限制，使用遞歸/回溯算法找到最大總和

這不是一個家庭作業，只是一個遞歸自我練習。 :)給定一個列表和一個限制，使用遞歸/回溯算法找到最大總和

問題：（http://practiceit.cs.washington.edu/problem.jsp?category=Building+Java+Programs%2C+3rd+edition%2FBJP3+Chapter+12&problem=bjp3-12-e21-maxSum）

給定一個整數表L和限制N，找到maxSum（L，N）不超過限制ñ。例如，L = [7,30,8,22,6,1,14]和極限n = 19，則maxSum（L，n）= 16。因爲最大組合是7 + 8 + 1 = 16。

我已經想通了經典的回溯算法來解決這個問題：

public static int maxSum(List<Integer> L, int limit){ 
     boolean[] used = new boolean[L.size()]; 
     int[] max = {0}; 
     rec(L, limit, 0, used, max); 
     return max[0]; 
    } 

    public static boolean rec(List<Integer> L, int limit, int cur, boolean[] used, int[] max){ 
     if(cur > limit){ 
      return false; 
     } 

     for(int i=0; i<L.size(); i++){ 
      if(!used[i]){ 
       used[i] = true; 
       if(rec(L, limit, cur+L.get(i), used, max)){ 
        max[0] = Math.max(max[0], cur+L.get(i)); 
       } 
       used[i] = false; 
      } 
     } 
     return true; 
    }

然而，由於這個問題不允許在程序中的任何循環。所以我想知道是否有辦法去除我的rec（）函數中的for循環。非常感謝！

來源

2013-11-29 Think Recursively

總有一種方法可以將循環重寫爲遞歸函數。值得注意的是，有些語言沒有循環，只有遞歸（例如Scheme，Prolog）。 [東西閱讀]（http://www.refactoring.com/catalog/replaceIterationWithRecursion.html） – Amadan

當然有可能，每個循環都可以用遞歸來替換。

for(int i = 0; i < size; i++) { 
    // some code goes here 
}

我們可以做迭代與下面的遞歸函數：

private void iterate(int i, int size) { 
    if (i == size){ 
    return; 
    } 
    // some code goes here 
    iterate(i+1, size); 
}

並開始通話將是：

iterate(0, size);

這將執行一些代碼爲每個i0..size。

來源

2013-11-29 02:13:43 Deximat

謝謝！很好解釋。我已經重寫了代碼！ –

基於@Deximat的建議，我重寫了代碼以刪除for循環，它的工作原理！

 public static int maxSum2(List<Integer> L, int limit){ 
      boolean[] used = new boolean[L.size()]; 
      int[] max = {0}; 
      rec2(L, limit, 0, used, max, 0); 
      return max[0]; 
     } 

     public static boolean rec2(List<Integer> L, int limit, int cur, boolean[] used, int[] max, int index){ 
      if(cur > limit){ 
       return false; 
      } 

      if(index == L.size()){ 
       return true; 
      } 
      if(!used[index]){ 
       used[index] = true; 
       if(rec2(L, limit, cur+L.get(index), used, max, index)){ 
        max[0] = Math.max(max[0], cur+L.get(index)); 
//      return true; 
       } 
       used[index] = false; 
      } 

      return rec2(L, limit, cur, used, max, index+1); 
     }

來源

2013-11-29 03:15:00

這個問題實際上可以在不使用其他方法的情況下解決。該概念如下：

如果列表爲空返回0
如果列表具有1個項目，這是< =極限返回項目
如果列表具有1個項目，這是>極限返回0
如果列表中有超過1項，第一項是>期限返還子表的最大
以其他方式限制減去第一項返回子列表的最大值和第一項加子列表的最大值之間的最大

public static int maxSum(List<Integer> numbers, int limit) { 

     if(numbers.size() == 0){ return 0; } 
     int num = numbers.get(0); 
     if(numbers.size() == 1){ 
     if(num > limit){ 
      return 0; 
     }else{ 
      return num; 
     } 
     } 
     List<Integer> sublist = numbers.subList(1, numbers.size()); 
     int subMax = maxSum(sublist, limit); 
     if(num > limit){ return subMax; } 
     int max = num + maxSum(sublist, limit - num); 
     return Math.max(max, subMax); 

}

來源

2016-10-04 17:23:04 gabeodess

給定一個列表和一個限制，使用遞歸/回溯算法找到最大總和

回答

相關問題