동적 프로그래밍 단계 추적하기

Question

저는 기본적인 프로그래밍 원리를 가르쳐 왔으며 동적 프로그래밍 문제에 봉착했습니다. 악의적 인 배낭 문제를 생각해 봅시다.

각 가중치와 값이있는 항목 집합이 주어지면 총 가중치가 주어진 제한보다 작거나 같도록 컬렉션에 포함 할 항목 수를 결정합니다 총 가치는 가능한 한 커집니다.

가중치 제한을 10으로 설정하고 weights = [2,4,7] 및 values ​​= [8,4,9]의 목록을 두 개 만듭니다 (방금 작성했습니다). 제약 조건에 따라 최대 값을 부여하는 코드를 작성할 수 있습니다. 이는 문제가 아닙니다. 그러나 내가 실제로 사용하게 된 가치를 알고 싶다면 어떨까요? 총 가치가 아닌 개별 가치. 이 예제에서 최대 값은 가중치가 2와 7 인 객체가 될 것이고 총 값은 8 + 9 = 17이 될 것입니다. 제 대답이 "17"을 읽는 것을 원하지는 않습니다 - 목록 출력을 원합니다. like : (8, 9). 이 문제는 쉽게 발생할 수 있지만, 제가 작업하고있는 문제는 목록이 훨씬 크고 반복되는 숫자를 사용합니다 (예 : 여러 개체의 값이 8).

누구든지 무엇이든 생각할 수 있으면 알려주세요. 항상 그렇듯이 지역 사회에 대한 많은 사랑과 감사.

Answer 1

각 부분 솔루션을 노드로 간주하십시오. 이 노드들 각각에 사용하는 것을 추가하기 만하면 끝나는 노드가 사용 된 항목 집합을 포함하게됩니다.

그래서 새로운 솔루션을 찾을 때마다 새로운 최적 솔루션의 항목 목록에 항목 목록을 설정하고 각각을 반복하면됩니다.

Answer 2

기본 배열 구현은 새 DP 상태에서 값을 가져올 수있는 항목을 추적하는 데 도움이됩니다. 예를 들어 DP 배열이 w[] 인 경우 다른 배열 p[]을 가질 수 있습니다. w[i]에 대한 상태가 생성 될 때마다 p[i]을 'w [i]'에 도달하는 데 사용한 항목으로 설정합니다. 그런 다음 w[n]에 사용 된 항목 목록을 출력하려면 p[n]을 출력 한 다음 0이 될 때까지 n-weightOf(p[n]) 색인으로 이동하여 모든 항목을 출력하십시오.