Distribute list of resources equally

Question

It's kind of hard to explain the problem I'm having but let's give it a try :)

The small game I'm working on creates a bunch of nodes that are filled with two kinds of resources.
Each node has an iron value and a gold value.

I want to divide these nodes into two areas, so both areas have about the same amount of gold. However, the difference in iron may not be greater than a certain number (let's pick 50 for this example)

The gold/iron ratios are pretty much random, by the way. Here's an example :

1. gold 75 iron 30

2. gold 35 iron 70

3. gold 65 iron 35

Solution for the above situation : 1 and 3 go to area1, 2 goes to area2.

I'm having a lot of trouble trying to automate this process. I've tried iterating through the list of nodes and always passing the node to the area with the smaller amount of iron but that almost never works.
Trying to reassign some nodes from the richer area proves difficult as well, since some nodes have well above 50 iron.
I don't necessarily need to find the best solution (the one with the smallest difference in gold), although that would be optimal.

Any ideas or input are appreciated.

Answer 1

I've had a bit of a play with this and this is what I've got so far, should give a good starting point. I've randomly generated a list of gold and iron pairs (I've used Point because it was simpler for me to work with but anything would work.)

The idea is to take a group of small value golds and swap them with a single larger value gold from the other list. Which in most cases will talk equivilent amounts of gold, but swap a larger value of iron with a smaller one.

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

And the result: