c# - 公平分享水果(动态规划)

Question

我很难弄清楚如何有效地解决这个问题。让我描述一下它是如何进行的:

“一位辛勤工作的妈妈为她的三个 child Amelia、Jessica 和 Bruno 买了几种营养值(value)不同的水果。两个女孩都超重，而且非常恶毒，总是让可怜的 Bruno 一无所有，所以他们的母亲决定分享食物的方式如下:

• Amelia 最重，获得的营养值(value)最高
• Jessica 获得的收入等于或少于 Amelia
• Bruno 的营养值(value)等于或低于 Jessica，但您需要找到一种方法，在遵守规则 (A >= J >= B) 的同时为他提供尽可能高的营养值(value)”

注:原问题描述不一样但是思路是一样的，不想让同学google求助的时候发现这个帖子呵呵。

我老师给出的一个测试用例如下:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1}

Input:
7   -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values

Output:
1 11  ---->  One fruit, their nutritional values sum for Amelia
5     ---->  Position of the fruit in the list
3 11  ---->  Three fruits, their nutritional values sum for Jessica
1 2 6 ---->  Position of the fruits in the list
3 10  ---->  Three fruits, their nutritional values sum for Bruno
3 4 7 ---->  Position of the fruits in the list

注意:我知道有几种方法可以让 children 吃水果，但只要遵循规则 A >= J >= B 就没关系。

起初我做了一个生成所有子集的算法，每个子集都有它们的总和，以及正在使用的位置。那个方法很快就被废弃了，因为水果列表最多可以有50个水果，而且子集算法是O(2^n)。我的内存用完了。

我的第二个想法是使用动态规划。在列标题中我会有水果列表的位置，在行标题中也是如此，这有点难以用字母解释所以我会提前为前面的例子做表格 { 4, 2, 1, 8 , 11, 5, 1}.

   00 01 02 03 04 05 06 07
00 
01
02
03
04
05
06
07

每次我们前进到下一行时，我们都会添加位置 1,2,3,...,7

   00 01 02 03 04 05 06 07
00 00                     <---No positions in use  
01 04                     <---RowPosition 1 + Column Position(Column 0) (4+0)
02 06                     <---RowPosition 1 + RowPosition 2 + Column Position (4+2+0)
03 07                     <---RP(1) + RP(2) + RP(3) + CP(0) (4+2+1+0)
04 15                     <--- (4+2+1+8+0)
05 26
06 31
07 32                     <--- (4+2+1+8+11+5+1+0)

现在你知道它是怎么回事了，让我们添加第一行

   00 01 02 03 04 05 06 07
00 00 04 02 01 08 11 05 01   <-- Sum of RP + CP                     
01 04 00 06 05 12 15 09 05   <-- Sum of RP(0..1) + CP                      
02 06                     
03 07                     
04 15                     
05 26
06 31
07 32                     

我输入 00 是因为第 1 个位置已被占用。完成的表格如下所示。

   00 01 02 03 04 05 06 07
00 00 04 02 01 08 11 05 01                      
01 04 00 06 05 12 15 09 05                         
02 06 00 00 07 14 17 11 07                 
03 07 00 00 00 15 18 12 08                  
04 15 00 00 00 00 26 20 16                    
05 26 00 00 00 00 00 31 27
06 31 00 00 00 00 00 00 32
07 32 00 00 00 00 00 00 00    

现在我们有了 table 。我将营养值(value)的总和除以 child 的数量，32/3 = 10.6667，上限为 11。我尝试检查 11，如果它在表中，我选择它并标记行的位置和使用的表的列，然后我会尝试再次检查 11，如果它在表中，我会选择它，否则查看 10 或 9 等，直到找到它。之后我会将各自的位置标记为已使用，然后将未使用的位置相加以获得布鲁诺的水果。

我知道必须有更好的方法来做到这一点，因为我发现我的方法有一个缺陷，该表只有几个子集的总和。所以也许这在一些测试用例中是有害的。也许是 3D Memoization Cube？，我认为它会消耗太多内存，而且我有 256MB 的限制。

哇，我没有意识到我输入了这么多 x.X。我希望我不会得到很多 tl；博士任何帮助/指南将不胜感激:D

编辑:我编写了生成表格的代码，以防有人想尝试一下。

static void TableGen(int[] Fruits)
    {
        int n = Fruits.Length + 1;
        int[,] memo = new int[n, n];

        for (int i = 1; i < n; i++)
        {
            memo[0, i] = Fruits[i - 1]; 
            memo[i, 0] = memo[i - 1, 0] + Fruits[i - 1]; 

            for (int j = i + 1; j < n; j++)
                memo[i, j] = memo[i, 0] + Fruits[j - 1];               
        }


        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                Console.Write("{0:00} ", memo[i, j]);

            Console.WriteLine();
        }

    }

Answer 1

一种计算量稍大的方法是以循环方式分配水果，从阿米莉亚的最高营养值(value)开始。
从那里开始，从 amelia 持有的最低营养值(value)开始逐步循环水果，并尝试(a)将水果给 jessica 或(b)将水果与 jessica 持有的水果交换的每种组合，同时仍然满足规则。然后对杰西卡和布鲁诺应用同样的方法。重复这 2 个循环，直到没有更多的交换或给予是可能的。
稍微棘手但可能更快的是同时给予/交换给 jess/bruno。对于 A 持有的每 2 个水果，您将有 4 个选项可以尝试，如果您同时尝试平衡 J 和 B，则可以尝试更多选项。

要获得更快的算法，您可以尝试在数学堆栈交换站点上询问，因为这在很大程度上是一个集合论问题。