Which items were selected during Unbounded Knapsack algorithm?

user_10705221 0
Viewed 427

I am using 1D array to get the final answer, but I also need to get selected items. How to achieve that?

    private static int UnboundedKnapsack(int capacity, int n, int[] itemValue, int[] itemWeight)
    {
        int[] dp = new int[capacity + 1];

        for (int i = 0; i <= capacity; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (itemWeight[j] <= i)
                {
                    dp[i] = Math.Max(dp[i], dp[i - itemWeight[j]] + itemValue[j]);
                }
            }

        }
        return dp[capacity];
    }
dynamic-programming
1 Answers

Let's introduce a new path function that gives the optimal selcetions of items using the previously calculated dp array.

private static void path(int capacity, int n, int[] itemValue, int[] itemWeight, int[] dp){
    if(capacity == 0) return; // here you handle when the function will end. I assume capacity should be empty at the last
    int ans = 0, chosenItem;
    for(int j = 0; j < n; j++){
        int newAns = dp[capacity - itemWeight[j]] + itemValue[j];
        if(newAns > ans){
            ans = newAns;
            chosenItem = j;
        }
    }
    printf("%d ",chosenItem); // here you get the current item you need to select;

    path(capacity - itemWeight[chosenItem], n, itemValue, itemWeight, dp);

}
user_90384300
Related