CODEWITHSUNDEEP
c#
user285372
user285372

Reputation:

Dividing up a long list of numbers and figuring out the minimum summation of each chunk

I have been working on three small programs that extract all the sub-strings of a given string (or even a list of integers) as well as all the different combinations of their elements. I now understand them...

My aim to start like this (originally) was to see if I can solve a puzzle, by learning these programs. Here is the puzzle:

Say I am trekking and I have 6 walking distances { 11, 16, 5, 5, 12, 10 } that I would like to finish within 3 days. So, I can do 11 and 16 kilometers during day 1, 5 and 5 kilometers during day 2, and finally 12 and 10 kilometers during day 3.

Perhaps I could do only 11 kilometers during day 1, 16 and 5 and 5 kilometers during day 2, and 12 and 10 kilometers during day 3.

etc . . . etc . . .

My goal is to work out the "minimum" walked distance over the course of these three days. So, in this example, 11 in day 1 and 26 in day 2 and 22 in day 3 would give a maximum of 26, and that 26 is actually the minimum - it does not get better than this.

No matter what combination of three chunks (days) I choose, the daily walked distance doe not get less than 26. For example, if I choose 11+16 for day 1 and 5+5 for day 2 and 12+10 for days 3, I am looking at a max of 27.

However, I cannot quite figure out how to divide up the list elements in 3, which is the number of days. If it was four, I could have four chunks with arbitrary number of distances in each day. And then add up all the divided elements and see which maximum comes out as minimum.

I appreciate this might be a too-big-a-bite for me at this point (I can just about understand the programs that I have put below) but I was wondering if someone perhaps could help me understand this and help me write a function that can handle any number of days and walking stages.

All I have been able to produce so far is a function that can print all the sub-lists and combinations of these 6 walking stages...

    static void Main(string[] args)
    {
        string str = Console.ReadLine();

        for (int i = 1; i <= str.Length; i++)
        {
            for (int j = 0; j <= (str.Length - i); j++)
            {
                string subStr = str.Substring(j, i);
                Console.WriteLine(subStr);
            }
        }

        Console.ReadLine();
    }



    static void Main(string[] args)
    {
        List<int> list = new List<int>() { 11, 16, 5, 5, 12, 10 };

        for (int i = 0; i <= list.Count-1; i++)
        {
            for (int j = 0; j <= list.Count-i; j++)
            {
                string subList = string.Concat( list.GetRange(i, j) );
                Console.WriteLine(subList);
            }
        }

        Console.ReadLine();
    }



    static void Main(string[] args)
    {
        GetCombination( new List<int> { 11, 16, 5, 5, 12, 10 } );

        Console.ReadLine();
    }

    static void GetCombination( List<int> list )
    {
        double count = Math.Pow(2, list.Count);

        for (int i = 1; i <= (count-1); i++)
        {
            string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');

            for (int j = 0; j < str.Length; j++)
            {
                if ( str[j] == '1' )
                {
                    Console.Write( list[j] );
                }
            }

            Console.WriteLine();
        }
    }

Upvotes: 1

Views: 44

Answers (1)

just.ru
just.ru

Reputation: 648

This problem can be solved by dynamic programming. Here is my code for it with top-down approach:

class Program
{
    static void Main(string[] args)
    {
        int[] array = { 11, 16, 5, 5, 12, 10 };
        // change last parameter to the number or days
        int min = MinDistance(array, 0, 0, 3); 
        Console.WriteLine(min);
    }

    static int MinDistance(int[] array, int day, int prevDayDistance, int daysLeft)
    {
        if (day == array.Length)
        {
            return prevDayDistance;
        }
        if (daysLeft == 0)
        {
            return int.MaxValue;
        }

        // Keep walking.
        int keepWalkResult = MinDistance(array, day + 1, prevDayDistance + array[day], daysLeft);

        // Postpone it to the next day.
        int sleepResult = MinDistance(array, day, 0, daysLeft - 1);

        // Choose the best solution.
        return Math.Min(keepWalkResult, Math.Max(prevDayDistance, sleepResult));
    }
}

For big input arrays you can consider caching MinDistance results for triples (day,prevDayDistance,daysLeft).

Upvotes: 1

Related Questions