배낭 알고리즘의 최적 솔루션에 포함된 특정 항목을 어떻게 검색할 수 있나요?

Knapsack 알고리즘에서 요소 검색

Knapsack 알고리즘은 제약 조건이 있는 항목 집합에서 달성할 수 있는 최적의 값을 효율적으로 결정합니다. 그러나 어떤 항목이 기여하는지 지정하지 않고 전체 값만 제공합니다.

최적 솔루션에 포함된 특정 요소를 얻으려면 알고리즘 내에서 다음 단계를 따르세요.

for (size_t j = 1; j <= n; j++)
{
    for ( int w = 1; w <= W; w++)
    {
        ...
        if (dp[w][j] != dp[w][j-1] && dp[w][j] == dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight())
        {
            // Mark element 'j' as included in the solution
        }
    }
}

이것은 단계는 현재 값을 이전 값과 비교하여 솔루션에 항목이 추가된 시기를 식별합니다. 선택한 요소는 가중치와 동일한 연속 값 간의 차이를 만듭니다.

또는 알고리즘이 실행된 후 역행렬을 탐색하여 선택한 항목을 확인할 수 있습니다.

int line = W;
int i = n;
while (i > 0):
    if (dp[line][i] - dp[line - weight(i)][i-1] == item[i].getValue()):
        // Item 'i' is in the solution
        i--;
        line -= weight(i);
    else:
        i--;

이 접근 방식은 최적의 솔루션에 기여하는 요소를 효율적으로 검색하여 문제 솔루션에 대한 보다 포괄적인 통찰력을 제공합니다.

위 내용은 배낭 알고리즘의 최적 솔루션에 포함된 특정 항목을 어떻게 검색할 수 있나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!