균형 파티션 욕심 접근법

Question

균형 분배 문제 here과 here (problem 7)이 있습니다.

문제는 기본적으로 주어진 숫자 배열을 2 개의 부분 집합 (S1과 S2)으로 분할하여 숫자의 합계 사이의 절대 차이가 S1이되도록 요구합니다. ans S2 |sum(S1) - sum(S2)|은 최소가되어야합니다. 내가 이해하지 못했던 한 가지는 욕심 많은 접근법을 제안하지 않는 이유입니다.

def balanced_partition(lst): 
    idx = 0 
    S1 = 0 
    S2 = 0 
    result_partition=[None]*len(lst) 
    while idx < len(lst): 
     new_S1 = S1 + lst[idx] 
     new_S2 = S2 + lst[idx] 
     if abs(new_S1 - S2) < abs(new_S2 - S1): 
      result_partition[idx] = 1 
      S1 = new_S1 
     else: 
      result_partition[idx] = 2 
      S2 = new_S2 
     idx += 1 
    print("final sums s1 = {S1} and s2 = {S2} ".format(S1=S1, S2=S2)) 
    return result_partition 

내 접근 방식에 어떤 문제가 있습니까? 내가 얻을 수있는 모든 테스트 케이스를 통과 한 것 같습니다.

Answer 1

간단한 반례는 [1,1,1,1,1,1,6]입니다. 욕심 많은 접근 방식은 두 세트 사이에 확산되며 최적 솔루션은 [1,1,1,1,1,1], [6]입니다.

Answer 2

구현 및 접근 방법에는 아무런 문제가 없습니다. 그러나이 특정 문제에서 모든 하위 집합을 고려하면 욕심 많은 결과보다 더 나은 대답을 찾을 수 있습니다. 당신이 공유 한 위키 페이지조차도 몇 가지 예를 가지고 있습니다.

아마 두 방법의 차이점을 이미 알고있을 것입니다. 욕심 많은 알고리즘은 항상 좋은 결과를 줄 것입니다. 가깝거나 같을 수도 있지만 모든 옵션을 고려해야합니다. 동적 프로그래밍 접근법은 모든 가능한 부분 집합을 한 방법으로 검사합니다. 이전에 계산 된 하위 문제의 결과를 저장하므로 기본적으로 무차별 강제력보다 빠릅니다.

질문은 욕심이 많거나 동적 프로그래밍 방식을 사용하는 경우입니다. 나는 경쟁적인 프로그래밍을 해왔고 DP 문제 (파티셔닝, 서브 셋 합, 배낭과 같은 문제)를 보았을 때, 때로는 좀 더 분명하기 때문에 때로는 탐욕스러운 해결책을 제시하기도합니다. 사람들은 매일 욕심 많은 접근 방식을 사용합니다. 구현하기 전에 예제를 사용하여 알고리즘을 테스트하고 이것이 올바른 접근 방식이라고 확신한다면 구현합니다. 어떤면에서는 다소 직관적입니다.

더 나은 답변이 필요한 테스트 케이스를 찾으면 대부분 DP 솔루션을 찾아야한다는 것을 의미합니다. 판단 시스템에서 WA를 얻은 경우, 좋은 테스트 케이스를 찾지 못했음을 의미합니다.하지만 더 나은 솔루션을 찾는 데 도움이되지 않기 때문에 정확한 테스트 케이스를 찾을 필요가 없습니다.