최적의 배낭 솔루션에 포함된 특정 품목을 어떻게 식별할 수 있습니까?

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

NP-하드 빈 포장 문제에 대한 솔루션인 배낭 알고리즘이 최적 배낭 솔루션을 계산합니다. 제한된 용량의 항목 집합에서 얻을 수 있는 가치입니다. 그러나 어떤 특정 항목이 이 최적의 솔루션에 기여하는지 사용자가 궁금해하는 경우가 많습니다.

이 문제를 해결하기 위해 배낭 알고리즘을 수정하여 최적화 프로세스 중에 선택된 요소를 추적할 수 있습니다. 이는 솔루션의 가치에만 의존하기보다는 최적의 솔루션을 구성하는 항목을 식별하는 직접적인 방법을 제공합니다.

접근 방식:

1. 추가 항목 만들기 선택된 행렬. 여기서 selected[w][j]는 인덱스 j-1의 요소가 용량 w에서 선택되었는지 여부를 나타냅니다.
2. 초기화 선택한 행렬을 0으로 설정합니다.
3. knapsack 알고리즘 중에 dp[w][j]를 업데이트할 때 items[j-1]이 선택되면 selected[w][j]도 1로 설정합니다(dp[ w][j] = dp[w - items[j-1].getWeight()][j-1] items[j-1].getWeight()) 이 요소가 변경되었음을 나타냅니다. 선택되었습니다.
4. 최적 값을 결정한 후 선택한 매트릭스를 추적하여 선택한 특정 항목을 식별합니다.

의사 코드:

int Knapsack::knapsack(std::vector<Item>& items, int W)
{
    size_t n = items.size();
    std::vector<std::vector<int>> dp(W + 1, std::vector<int>(n + 1, 0));
    std::vector<std::vector<int>> selected(W + 1, std::vector<int>(n + 1, 0));
    for (size_t j = 1; j <= n; j++)
    {
        for (int w = 1; w <= W; w++)
        {
            if (items[j-1].getWeight() <= w)
            {
                dp[w][j] = std::max(dp[w][j-1], dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight());
                selected[w][j] = (dp[w][j] != dp[w][j-1]);
            }
            else
            {
                dp[w][j] = dp[w][j - 1];
            }
        }
    }

    // Identify selected items
    std::vector<int> takenItems;
    int line = W;
    int i = n;
    while (i > 0) {
      if (selected[line][i]) {
        takenItems.push_back(items[i-1].getIndex()); // Index of item taken
        line -= items[i-1].getWeight();
      }
      i--;
    }

    return dp[W][n];
}

이 향상된 배낭 알고리즘을 통해 최적 값뿐만 아니라 해당 최적 값에 기여하는 특정 요소도 식별할 수 있습니다. 솔루션.

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