Как узнать, какие вещи берут в 2 рюкзака?

Question

Эта функция принимает:

1. car1_laod : размер KnapSack1.
2. car2_load : размер KnapSack2.
3. N : количество предметов в магазине.
4. нагрузка : массив, который переносит вес предметов.
5. цена : массив, в котором указана цена предметов.
6. car1_items : список, содержащий элементы, которые я выбрал и поместил в car1.
7. car2_items : список, в котором указаны элементы, которые я выбрал и поместил в car2.

Цель состоит в том, чтобы узнать максимальную прибыль, которую я могу получить, добавив элементы в элементы car1 и car2, и их нельзя выбрать дважды.

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

Пример:

Ввод:

N = 4, car1_load = 5, car2_load = 2

Нагрузки [4] = {1,2,3,5}

цены [4] = {20,10,15,25}

Вывод:

Элементы, которые будут вставлены в списки, являются индексами [на основе 1] продуктов, выбранных для загрузки в оба варианта.rs

Прибыль = 45

Car1 items = [2, 3]

Car2 items = [1]

Мой вывод:

Пример вывода функции

Я рассчитал максимальную прибыль.

Проблема в том, что я не знаю, как отследить массив dp, чтобы узнать, где находитсяПришли вещи.

Answer 1

Вы должны добавить другое измерение к вашему массиву для индекса предмета, аналогично динамическому программному решению для обычной задачи о ранце (вы можете вычислить его без этого,но, по крайней мере, это будет сложнее).

Я оставлю детали для вас, но это даст вам что-то вроде этого:

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

Теперь вам нужноначните с конца и несколько раз выясните, какое из приведенных выше значений было максимальным, и продолжите с этим значением.

Это можно сделать, просто проверив, равна ли левая часть любому из значений нас правой стороны.

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
}

Код может немного отличаться от этого, в зависимости от того, как вы фактически изменили свой код, добавив индекс элемента в качестве измерения массива.