최적의 배낭 솔루션에 포함된 품목을 어떻게 효율적으로 결정할 수 있습니까?

최적 배낭 솔루션의 요소 결정

주어진 배낭 알고리즘은 빈 포장 문제에 대한 최적 값을 효율적으로 계산합니다. 그러나 당면 과제는 이 최적의 솔루션을 구성하는 요소를 식별하는 것입니다.

1. 선택 추적:

dp 행렬에서 최적의 값을 계산한 후 역추적하여 선택한 요소를 결정할 수 있습니다.

dp_copy = dp;  // Copy the dp matrix for backtracking

int weight_idx = W;
int item_idx = n;

while (weight_idx > 0 && item_idx > 0):
    if dp_copy[weight_idx][item_idx] != dp_copy[weight_idx - items[item_idx - 1].getWeight()][item_idx - 1]:
        // Element 'item_idx' is included in the optimal solution
        weight_idx -= items[item_idx - 1].getWeight()
        item_idx -= 1

2. 의사 코드 해석:

• 마지막 셀부터 첫 번째 셀까지 역순으로 dp 행렬을 반복합니다.
• 현재 셀과 차이가 있는지 확인합니다. 행렬의 위쪽 왼쪽에 있는 셀은 해당 항목의 가중치와 같습니다.
• 그렇다면 해당 셀 값과 연결된 항목은 다음과 같습니다. 솔루션에 포함됩니다.
• 추가로 역추적할 수 있도록 가중치 지수와 아이템 지수를 적절히 조정합니다.

3. 복잡도:

이 역추적 접근 방식에는 O(W * n) 시간 복잡도가 필요합니다. 여기서 W는 가방 용량이고 n은 항목 수입니다. 행렬의 각 셀을 한 번 반복하고 일정한 시간 검색 작업을 수행합니다.

위 내용은 최적의 배낭 솔루션에 포함된 품목을 어떻게 효율적으로 결정할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!