如何检索背包算法最优解中包含的具体项？

从背包算法中检索元素

背包算法有效地确定从一组具有约束的项目中可实现的最佳值。但是，它只提供总值，而没有指定哪些项目对其有贡献。

要获取最佳解决方案中包含的特定元素，请按照算法中的以下步骤操作：

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中文网其他相关文章！