c# - 如何知道2个背包问题中拿了哪些元素？

Question

这个函数需要:

1. car1_laod:KnapSack1 尺寸。
2. car2_load:KnapSack2 尺寸。
3. N:商店中的商品数量。
4. load:承载元素权重的数组。
5. price:包含商品价格的数组。
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]

利润 = 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
}

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