分配資源的列表同樣

Question

這是一種很難解釋我有這個問題，但讓我們給它一個嘗試:)

的小遊戲，我的工作產生了一堆的節點方式填充有兩個種類的資源。
每個節點都有一個iron值和一個gold值。

我想將這些節點分成兩個區域，所以兩個區域都有大約相同數量的gold。然而，在iron的差異可能不超過一定數目較大（讓我們挑50在這個例子中）

的gold/iron比率是非常隨機的，順便說一句。這裏有一個例子：

1. 金75鐵30

2. 金35鐵70

3. 金65鐵35

解決方案對於上述情況：1和3去到area1,2去area2。

我在嘗試自動執行此過程時遇到了很多麻煩。我已經嘗試遍歷節點列表，並始終將節點傳遞到數量較少的區域，但幾乎從不運行。
嘗試從更豐富的區域重新分配某些節點也很困難，因爲某些節點的性能遠高於50 iron。
我不一定需要找到最佳解決方案（gold中差異最小的解決方案），儘管這是最佳解決方案。

任何想法或輸入讚賞。

Answer 1

我已經有了一點玩這個，這是我迄今爲止，應該給一個很好的起點。我隨機生成了一個黃金和鐵對列表（我用過Point，因爲這對我來說工作起來更簡單，但任何工作都可以）。

這個想法是採取一組小值黃金和交換他們從另一個列表中獲得一個較大的黃金價值。在大多數情況下，會談論相當數量的黃金，但將較大的價值換成較小的黃金。

private void button2_Click(object sender, EventArgs e) 
    { 
     var GoldIron = new List<Point>(
     new Point[]{ 
     new Point(16,23),new Point(16,28),new Point(19,44),new Point(21,29), 
     new Point(23,16),new Point(24,82),new Point(27,85),new Point(31,63), 
     new Point(31,78),new Point(32,65),new Point(41,23),new Point(43,79), 
     new Point(44,76),new Point(45,23),new Point(47,16),new Point(50,15), 
     new Point(50,37),new Point(52,28),new Point(52,58),new Point(52,71), 
     new Point(61,39),new Point(61,75),new Point(63,59),new Point(68,25), 
     new Point(68,61),new Point(70,24),new Point(71,75),new Point(74,78), 
     new Point(77,59),new Point(82,27)} 
     ); 
     listBox1.DataSource = GoldIron; 
     //Split into 2 lists based on the gold amount 
     var Left = new List<Point>(); 
     var Right = new List<Point>(); 
     var SumGold = GoldIron.Sum(P => P.X); 
     var SumIron = GoldIron.Sum(P => P.Y); 
     label2.Text = SumGold.ToString(); 
     label1.Text = SumIron.ToString(); 
     var LeftGold = 0; 
     Int32 i = 0; 
     while (LeftGold < SumGold/2) 
     { 
      LeftGold += GoldIron[i].X; 
      Left.Add(GoldIron[i++]); 
     } 
     while (i < GoldIron.Count) 
     { 
      Right.Add(GoldIron[i++]); 
     } 

     Int32 LIndex = 0; 
     //Start Algorithm 
     Int32 LeftIron = Left.Sum(P => P.Y); 
     Int32 RightIron = Right.Sum(P => P.Y); 
     while (LeftIron - RightIron > 50 || RightIron - LeftIron > 50) 
     { 

      if (LeftIron < RightIron) 
      { 
       List<Point> TempList = Left; 
       Left = Right; 
       Right = TempList; 
       LIndex = 0; 
      } 
      Int32 SmallestRight = Right[LIndex].X; 
      LeftGold = 0; 
      i = 0; 
      while (LeftGold < SmallestRight) 
      { 
       LeftGold += Right[i++].X; 
      } 
      Point Temp = Right[LIndex]; 
      Right.RemoveAt(LIndex); 
      Right.AddRange(Left.Take(i)); 
      Left.RemoveRange(0, i); 
      Left.Add(Temp); 
      LIndex += i; 
      //Sort 
      Left.Sort(CompareGold); 
      Right.Sort(CompareGold); 
      LeftIron = Left.Sum(P => P.Y); 
      RightIron = Right.Sum(P => P.Y); 
     } 
     listBox2.DataSource = Left; 
     SumGold = Left.Sum(P => P.X); 
     SumIron = Left.Sum(P => P.Y); 
     label4.Text = SumGold.ToString(); 
     label3.Text = SumIron.ToString(); 
     listBox3.DataSource = Right; 
     SumGold = Right.Sum(P => P.X); 
     SumIron = Right.Sum(P => P.Y); 
     label6.Text = SumGold.ToString(); 
     label5.Text = SumIron.ToString(); 
    } 

而結果：