6

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

“一位勤劳的妈妈为她的 3 个孩子 Amelia、Jessica 和 Bruno 买了几种营养价值不同的水果。两个女孩都超重，而且她们非常恶毒，总是让可怜的布鲁诺一无所有，所以他们的母亲决定分享食物以下方式：

  • 阿米莉亚是最重的人获得最多的营养价值
  • 杰西卡得到的金额等于或少于阿米莉亚
  • 布鲁诺得到的数量等于或少于杰西卡，但你需要找到一种方法，在尊重规则的同时给他尽可能高的营养价值（A >= J >= B）”

注意：原问题描述不同，但思路是一样的，我不希望我的同学在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

注意：我知道在孩子们中间有几种挖水果的方法，但只要遵循规则 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，因为第一个位置已经在使用中。完成的表格将如下所示。

   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

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

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

哇，我没有意识到我输入了这么多 xX 我希望我不会得到很多 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();
        }

    }
4

2 回答 2

1

一种稍微计算密集型的方法是以循环方式分配水果，从阿米莉亚的最高营养价值开始。
从那里开始，逐步遍历 amelia 持有的最低营养价值的水果，并尝试以下两种组合：(a) 将水果交给 jessica，或 (b) 将水果与 jessica 持有的水果交换，同时仍然满足规则。然后对 jessica 和 bruno 应用相同的方法。重复这 2 个循环，直到不再有交换或给予是可能的。
稍微棘手但可能更快的方法是同时给予/交换给 jess/bruno。对于 A 持有的每 2 个水果，您将有 4 个选项可供尝试，如果您同时尝试平衡 J & B，则可以选择更多。

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

于 2012-07-02T00:28:59.290 回答
1 
    for(i = 0; i < count; i++)
    {
    currentFruit=Fruits.Max();

    if(Amelia.Sum() + currentFruit < Jessica.Sum() + currentFruit)
        {
        Amelia.Add(currentFruit);
        Fruits.Remove(currentFruit);
        continue;
        }
    if(Jessica.Sum() + currentFruit < Bruno.Sum() + currentFruit)
        {
        Jessica.Add(currentFruit);
        Fruits.Remove(currentFruit);
        continue;
        }
    Bruno.Add(currentFruit);
    Fruits.Remove(currentFruit);
    }

这适用于具有相对相似值的水果。如果您添加的水果的价值大于所有其他水果的总和（我偶然做过一次），它会有点崩溃。

于 2012-07-01T09:53:24.820 回答