如何檢索背包演算法最優解所包含的具體項？

從背包演算法中檢索元素

背包演算法有效地確定從一組具有約束的項目中可實現的最佳值。但是，它只提供總值，而沒有指定哪些項目對其有貢獻。

要取得最佳解決方案中包含的特定元素，請按照演算法中的以下步驟操作：

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中文網其他相關文章！