分享水果相當（動態編程）

我很難找出如何有效解決這個問題。讓我描述一下它是如何發展的：分享水果相當（動態編程）

「一位辛勤工作的媽媽爲她的3個孩子阿米莉亞，傑西卡和布魯諾買了幾種不同營養價值的水果，兩個女孩都超重，他們非常惡毒，總是讓布魯諾什麼都沒有，所以他們的母親決定分享食物以下列方式：

阿梅利亞是最重的一個得到最大量的營養價值
傑西卡得到的金額等於或小於阿梅利亞
布魯諾得到等於或小於傑西卡的金額，但你需要找到一種方法給他（A> = J> = B）

注意：最初的問題描述不同，但想法是相同的，我不想讓我的同學找到這篇文章當他們谷歌幫助嘿嘿。

一個由我的老師給出的測試案例如下：

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）。我用完了內存。

我擁有的第二個想法是使用動態規劃。在列標題中，我將擁有Fruit列表中的位置，在行標題中相同，這很難用字母來解釋，所以我會提前做一個前面例子的表格{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等，直到找到它。之後，我會標記所使用的各個位置，然後總結未使用的位置以獲得Bruno的成果。

我知道必須有更好的方法來做到這一點，因爲我在我的方法中發現了一個缺陷，表中只有幾個子集的總和。所以也許這在少數測試案例中是有害的。也許是一個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(); 
     } 

    }

來源

2012-07-01 Julian J. Tejera

示例輸出不符合指定的規則。 –

「阿米莉亞是最重的一個獲得最多的水果」，這意味着你需要給她最多的營養價值或FruitCount？ – Jester

是否有其他規則可以省略？否則，只給Amelia最高的NV項目，下一個Jessica，然後給Bruno。重複，直到你沒有食物。這會給你A> = J> = B，但不能使它們的總值儘可能接近。 – Michael

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-01 09:53:24 impyre

看起來你很難創建網格......爲什麼？ – impyre

一個稍微計算密集的方法是以循環方式分配水果，從最高的營養價值開始。
從那裏開始逐漸循環從amelia所持有的最低營養價值的果實中，嘗試（a）將果實交給傑西卡，或者（b）將果實與傑西卡持有的果實交換，同時仍然滿足規則。然後將相同的方法應用於jessica和bruno。重複這兩個循環，直到沒有更多的掉期或給出是可能的。
稍微複雜一點，但可能更快，將同時給/交換到傑斯/布魯諾。對於每個2個A的水果，您將有4個選項可供選擇，如果您同時嘗試和平衡，則更多選擇J & B.

對於更快的算法，您可以嘗試詢問數學堆棧交換網站，因爲這是一個非常集合論的問題。

來源

2012-07-02 00:28:59 3Pi

分享水果相當（動態編程）

回答

相關問題