재귀 워드 랩 알고리즘

Question

나는 세 부분으로 구성된 알고리즘을 연구 중이다. 첫 번째는 최소 길이의 페널티를 사용하여 단어를 특정 길이로 줄이는 재귀 적 방법입니다. 두 번째는 재귀 적 메서드의 동적 구현 인 알고리즘입니다. 마지막 것은 문제의 욕심 많은 알고리즘입니다. 이미 Greedy 코드가 코딩되어 있지만 Recursive 솔루션에 어려움을 겪고 있습니다. 정확히 어디에서 정확히 재귀 적 방법으로 문제가 발생하는지 모르겠지만 Knuth-Plass Algorithm과 비슷한 것이어야합니다. 재귀 알고리즘은 계승 실행 시간을 가지며 동적 솔루션을 돕는 데 더 많이 사용됩니다. 누구나 Knuth-Plass 구현에 대한 링크가 있거나 내 코드에서 거대한 것을 발견 할 수 있다면 어떤 도움을 주시면 감사하겠습니다.

재귀 알고리즘 :

public static ArrayList<String> recursive(ArrayList<String> input, int size) { 
    if(input.size() <= 1) 
     return input; 
    ArrayList<String> temp1 = input; 
    ArrayList<String> temp2 = input; 
    for(int i = 0; i < input.size(); i++) { 
     if(input.size() - 1 >= size) 
      break; 
     else { 
      for(int j = 0; j < input.size(); j++) { 
       temp1.set(j, temp1.get(j) + " " + temp1.get(j + 1)); 
       temp1.remove(j + 1); 
       if(totalPenalty(blankChars(temp1, size)) < totalPenalty(blankChars(temp2, size))) { 
        input = recursive(temp1, size); 
       } else { 
        input = recursive(temp2, size); 
       } 
      } 
     } 
    } 
    return input; 
} 

totalPenalty() 및 blankChars 각 행의 끝에 페널티의 양을 리턴한다.

편집 : 아직 해결 방법이 없습니다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

Java와 비슷하지만 Java에서는 암시 적 복사 생성자가 없습니다.

ArrayList<String> temp1 = input; < -이 하지 동일한 내용을 가진 다른 객체를 생성하지만 것 대신에 동일한 개체에 대한 참조.

ArrayList<String> temp1 = new ArrayList<String>(input); 
ArrayList<String> temp2 = new ArrayList<String>(input); 

내가 다른 실수에 대해보고하지 않은, 그래서 이것을 시도하고 당신이 더 이상 문제가있을 경우 질문을 업데이트 :

당신은에 라인 4와 5를 변경해야합니다.

크 누스 패스 나누기 알고리즘 정보; Python 구현은 http://oedipus.sourceforge.net/texlib/에서 찾을 수 있습니다. 나는 그것에 대해 자세히 보지 않았지만 설명은 당신이 찾고있는 것으로 보인다.