자원의 목록을 배포 동등하게

Question

그것은 내가 데 문제를 설명하지만, 이제 그것을 시도 :

이

내가 일하고 있어요 작은 게임은 두 가지로 가득 노드의 무리를 만들어 줄 수 있도록 가지 어려운 자원의 종류.
각 노드는 iron 값이고 gold 값입니다.

이 두 노드를 두 영역으로 나누고 싶으므로 두 영역의 노드 수가 모두 인 약 gold 인 것이 좋습니다. 그러나 iron의 차이가 특정 수보다 큰 수 없습니다

gold/iron 비율이 거의 무작위, 그런데이다 (의이 예를 들어 50을 선택하자).

1. 금 75 철 (30)

2. 금 35 철 (70)

3. 금 65 철 위의 상황에 35

솔루션 : 1 및 3 가고 여기 예제 area1으로 변경하면 2은 area2이됩니다.

이 프로세스를 자동화하는 데 많은 어려움을 겪고 있습니다. 난 노드 목록을 통해 반복 시도하고 항상 적은 양의 iron 영역과 노드를 전달하지만 거의 작동하지 않습니다.
일부 노드는 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(); 
    } 

그리고 결과 :