如何知道2个背包问题中拿了哪些物品？

Question

这个函数需要：

car1_laod: KnapSack1 尺寸。
car2_load: KnapSack2 尺寸。
N: 商店中的物品数量。
load：承载物品权重的数组
price: 一个包含物品价格的数组。
car1_items：包含我在 car1 中挑选和放入的物品的列表。
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]

利润=45

Car1 项目 = [2, 3]

Car2 项 = [ 1 ]

我的输出：

Example output of the function

我计算了最大利润

问题是我不知道如何回溯 dp 数组以了解项目的来源。

Answer 1

你应该为项目索引添加另一个维度到你的数组，类似于 the dynamic programming solution to the regular knapsack problem（你可能没有这个就可以计算它，但是在至少它会更复杂）。

我会把细节留给你，但这会给你这样的东西：

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
}

代码可能看起来与此略有不同，具体取决于您实际更改代码以将项目索引添加为数组维度的方式。

如何知道2个背包问题中拿了哪些物品？

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

c#

algorithm

knapsack-problem