How to know what items are taken in 2 knapsack problem?

Question

This function takes:

1. car1_laod: KnapSack1 size.
2. car2_load: KnapSack2 size.
3. N: Number of items in the shop.
4. load: an array that carries the weight of the items.
5. price: an array that carries the price of the items.
6. car1_items: List that contains which items I picked and put inside car1.
7. car2_items: List that contains which items I picked and put inside car2.

The Goal is to know the max profit that I can get by adding items to car1 & car2 items cannot be selected twice.

    public static int GetMaximumProfit(int car1_load, int car2_load, int N, 
     int[] loads, int[] prices, List<int> car1_items, List<int> car2_items)
    {
        Console.WriteLine();
        int[,] dp = new int[car1_load+1, car2_load+1];
        for(int i=0;i<N;i++)
        {
            for (int ks1=car1_load;ks1>=0;ks1--)
            {
                for(int ks2 = car2_load;ks2>=0;ks2--)
                {
                    if (ks1 >= loads[i] && ks2 >= loads[i])
                    {
                        dp[ks1, ks2] = max(
                                       dp[ks1, ks2],
                                       dp[ks1 - loads[i], ks2] + prices[i],
                                       dp[ks1, ks2 - loads[i]] + prices[i]
                                        );
                    }
                    else if (ks1 >= loads[i])
                    {  
                        dp[ks1, ks2] = Math.Max(
                                       dp[ks1, ks2],
                                       dp[ks1 - loads[i], ks2] + prices[i]
                                        );
                    }
                    else if (ks2 >= loads[i])
                    {

                        dp[ks1, ks2] = Math.Max(
                                       dp[ks1, ks2],
                                       dp[ks1, ks2 - loads[i]] + prices[i]
                                        );
                    }

                }
            }



        }



        cout(dp);
        Console.WriteLine("Answer : " + dp[car1_load, car2_load]);

        return dp[car1_load,car2_load];
    }

Example:

Input:

N = 4, car1_load = 5, car2_load = 2

Loads[4] = {1,2,3,5}

prices[4]={20,10,15,25}

Output:

The items to be inserted in the lists are the indices [1-based] of products selected to be loaded in both cars

Profit = 45

Car1 items = [2, 3]

Car2 items = [ 1 ]

My output:

Example output of the function

I calculated the max profit.

The Problem is that I don't know how to backtrack on the dp array to know where the items came from.

Answer 1

You should add another dimension to your array for the item index, similar to the dynamic programming solution to the regular knapsack problem (you may be able to calculate it without this, but at the very least it's going to be more complex).

I'll leave the specifics to you, but that will give you something like this:

dp[i, ks1, ks2] = max(
    dp[i-1, ks1, ks2],
    dp[i-1, ks1 - loads[i], ks2] + prices[i],
    dp[i-1, ks1, ks2 - loads[i]] + prices[i]
);

Now you need to start at the end and repeatedly figure out which one of the above values was the maximum and continuing with that value.

This can be done by just checking whether the left-hand side is equal to any of the values on the right-hand side.

int ks1 = car1_load, ks2 = car2_load;
for (i = N; i > 0; i--)
{
    if (ks1 >= loads[i] && dp[i, ks1, ks2] == dp[i-1, ks1 - loads[i], ks2] + prices[i])
    {
        // Add i to car 1
        ks1 -= loads[i];
    }
    else if (ks2 >= loads[i] && dp[i, ks1, ks2] == dp[i-1, ks1, ks2 - loads[i]] + prices[i])
    {
        // Add i to car 2
        ks2 -= loads[i];
    }
    // if it's equal to dp[i-1, ks1, ks2], we don't need to do anything
}

The code may look a bit different than this, depending on how you actually changed your code to add the item index as an array dimension.