목록과 한도가 주어지면 회귀/역 추적 알고리즘을 사용하십시오. 최대 값 찾기

Question

이것은 숙제가 아니며 재귀에 대한 자기 연습입니다. :)

문제 : (http://practiceit.cs.washington.edu/problem.jsp?category=Building+Java+Programs%2C+3rd+edition%2FBJP3+Chapter+12&problem=bjp3-12-e21-maxSum)

한계 N을 초과하지 않는 정수리스트 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 루프를 제거하는 방법이 있는지 궁금하네요. 대단히 감사합니다!

Answer 1

물론 모든 루프가 재귀로 대체 될 수 있습니다.

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); 
} 

그리고 시작 호출은 다음과 같습니다 모든 i0..size에 대한 몇 가지 코드를 실행하는 것입니다

iterate(0, size); 

합니다.

Answer 2

@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); 
     } 

Answer 3

이 문제는 실제로 추가적인 방법을 사용하지 않고 해결할 수 있습니다. 다음과 같은 개념이다 : 목록 1 개 항목을 가지고 있으며,이 < 경우 목록이 비어 반환 0

이다

• 경우 = 제한 반환 항목
• 목록 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); 

}