How Can I Retrieve the Specific Items Included in the Optimal Solution of the Knapsack Algorithm?

Retrieving Elements from the Knapsack Algorithm

The Knapsack algorithm efficiently determines the optimal value achievable from a set of items with constraints. However, it only provides the total value without specifying which items contribute to it.

To obtain the specific elements included in the optimal solution, follow these steps within the algorithm:

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
        }
    }
}

This step compares the current value with the previous ones, identifying when an item has been added to the solution. A chosen element makes the difference between consecutive values equal to its weight.

Alternatively, after the algorithm has been executed, you can traverse the matrix in reverse to determine the items selected:

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--;

This approach efficiently retrieves the elements contributing to the optimal solution, providing a more comprehensive insight into the problem's solution.

The above is the detailed content of How Can I Retrieve the Specific Items Included in the Optimal Solution of the Knapsack Algorithm?. For more information, please follow other related articles on the PHP Chinese website!