平等分配资源清单

Question

我正在开发一个小游戏，它创建了一堆节点，并填充了两种资源。每个节点都有一个铁值和一个金值。

我想将这些节点分成两个区域，使得两个区域的金数量大约相同。但是，铁的差异可能不大于某个数字（让我们在此例中选择50）。

顺便说一句，金/铁比率基本上是随机的。以下是一个示例：

1. 金75 铁30

2. 金35 铁70

3. 金65 铁35

上述情况的解决方案：1和3进入区域1，2进入区域2。

我试图自动化这个过程，但遇到了很多问题。我尝试通过迭代节点列表并始终将节点传递到具有较小铁数量的区域，但几乎从来不起作用。尝试重新分配一些来自更富的区域的节点也很困难，因为有些节点的铁远高于50。
我不一定需要找到最佳解决方案（具有金差异最小的方案），尽管那将是最理想的。

欢迎提供任何想法或建议。

- user1756192

---

你最后一段话听起来像是你只想保持铁的差异在你的门槛以下，而金的数量并不重要？ - Jan

@Jan 不完全正确。黄金分配肯定要公平，但与保持铁差距在50以下相比并不那么重要。编辑：分配区域1：100铁，200黄金；区域2：50铁，200黄金比以下更好：区域1：100铁，500黄金；区域2：100铁，200黄金。 - user1756192

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();
    }

结果如下：

并显示结果：

- James Barrass

---

非常感谢，这看起来非常有前途！我现在就要试一下。 - user1756192