3

私が抱えている問題を説明するのはちょっと難しいですが、試してみましょう:)

私が取り組んでいる小さなゲームは、2 種類のリソースで満たされた多数のノードを作成します。
各ノードにはiron値と値がありgoldます。

これらのノードを 2 つの領域に分割したいので、両方の領域にほぼ同じ量の がありgoldます。ただし、 の差はiron特定の数を超えない場合があります (50この例で選択しましょう)。

ちなみに、gold/iron比率はかなりランダムです。例を次に示します。

  1. ゴールド 75 アイアン 30

  2. ゴールド 35 アイアン 70

  3. 金 65 鉄 35

上記の状況の解決策: 1and 3go to area1, go 2to area2.

このプロセスを自動化しようとすると、多くの問題が発生します。ノードのリストを繰り返し処理し、常にノードをより少ない量の領域に渡すことを試みましたironが、それはほとんど機能しません。
一部のノードは をはるかに上回っているため、よりリッチな領域からいくつかのノードを再割り当てしようとすることも困難50 ironです。
必ずしも最適解 ( の差が最小のもの) を見つける必要はありませんがgold、それが最適でしょう。

どんなアイデアや意見も歓迎します。

4

1 に答える 1

3

私はこれで少し遊びましたが、これは私がこれまでに得たものであり、良い出発点を与えるはずです. 金と鉄のペアのリストをランダムに生成しました (作業が簡単だったので 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();
    }

そして結果： ここに画像の説明を入力

于 2012-10-18T13:50:12.527 に答える