Проблема планирования работы в Java

Question

Я пишу задачу для решения графиков работы, но мне трудно понять, как.

The Wood Shop имеет резерв заказов на свою всемирно известную качалку (1 кресло на заказ). Есть несколько этапы изготовления кресла-качалки Baber ручной работы (например, резка деревянных деталей, сборка, шлифование, нанесение пятен, и нанесение лака).

Общее время, необходимое для изготовления стула, составляет 1 неделю. Однако так как стулья продаются в разных В регионах и на разных рынках сумма прибыли для каждого заказа может отличаться. Кроме того, существует крайний срок, связанный с каждым заказом. Компания будет получать прибыль только в том случае, если они уложатся в срок; в противном случае прибыль равна 0.

Напишите программу, которая определит оптимальный график для заказов, который принесет максимальную прибыль. Входной файл будет содержать один или несколько тестовых случаев. Первая строка в тестовом примере будет содержать целое число n (0 n 1000), которое представляет количество заказов, ожидающих рассмотрения.

Значение 0 для n указывает конец входного файла. Следующие n строк содержат по 3 натуральных числа. Первое целое число i - это номер заказа.

Все номера заказов для данного Тестовый случай уникален. Второе целое число представляет количество недель с этого момента до крайнего срока для меня го порядок. третье целое число представляет сумму прибыли, которую компания получит, если срок будет соблюден для го заказ.

То, что я прошу, - это алгоритм того, как мне следует решить эту проблему.

Для каждого теста во входном файле выходной файл должен выводить строку, в которой указывается сумма прибыли, полученной в результате выполнение заказов в оптимальном порядке.

Example Input File (sched.in)
7
1 3 40
2 1 35
3 1 30
4 3 25
5 1 20
6 3 15
7 2 10
4
3054 2 30
4099 1 35
3059 2 25
2098 1 40
0
Example Output File (sched.out)
100
70

Answer 1

Существует множество способов решить проблему магазина.Начните с прочтения статьи в Википедии, затем возьмите хорошую книгу по разработке алгоритмов.Ваш профессор, вероятно, может порекомендовать один.Я подозреваю, что динамическое программирование было бы хорошим способом приблизиться к этому, но будут и другие подходы.

Это сложная проблема, поэтому не ждите простого ответа.Многие люди до сих пор ищут способы эффективного решения этой проблемы.

Answer 2

Добро пожаловать в удивительный мир проблем полного планирования NP. Как только вы уменьшите масштаб, невозможно найти оптимальное решение в нашей жизни. Это не имеет значения, вам просто нужно найти лучшее решение в данный момент времени (победить планировщиков и другие программы).

Не пишите эти алгоритмы самостоятельно (если вы не являетесь экспертом с многолетним опытом). Используйте готовую библиотеку, которая специализируется на таких проблемах, как:

• Drools Planner (с открытым исходным кодом, ASL, Java)

• OpenTS

• cpsolver

Answer 3

Постулат вашей проблемы неполон. Необходимо знать, сколько стульев можно сделать за неделю. Может быть, вы можете сделать все сразу. Но давайте предположим, что вы можете сделать только один. Решение похоже на это.

основываясь на очень умных комментариях Кэмерона Скиннера, я изменяю свой ответ на это:

public class tarea
{         
    List<input> datas = new ArrayList<input>();

     class input
     {
         public int profit;
         public int deadline;
         public int index1;
         public int index2;
         public int sum() {return index1+index2;}
        /**
         * @param profit
         * @param deadline
         */
        public input(int deadline, int profit)
        {
            super();
            this.profit = profit;
            this.deadline = deadline;
        } 

     }


     public void readData1()
     {
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(1,1));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
         this.datas.add(new input(10,1000));
     }


     public void readData2()
     {/*
         3 40
         2 1 35
         3 1 30
         4 3 25
         5 1 20
         6 3 15
         7 2 10 */

         this.datas.add(new input(3,40));
         this.datas.add(new input(1,35));
         this.datas.add(new input(1,30));
         this.datas.add(new input(3,25));
         this.datas.add(new input(1,20));
         this.datas.add(new input(3,15));
         this.datas.add(new input(2,10));
     }

     public void readData3()
     {/*
     2 30
     4099 1 35
     3059 2 25
     2098 1 40*/

         this.datas.add(new input(2,30));
         this.datas.add(new input(1,35));
         this.datas.add(new input(2,25));
         this.datas.add(new input(1,40));
     }



     @SuppressWarnings("unchecked")
    public void sortbyprofit(List<input> datas)
     {
         Collections.sort(datas, new Comparator() {

            public int compare(Object o1, Object o2)
            {
                if(((input)(o1)).profit < ((input)(o2)).profit)
                    return 1;
                else if(((input)(o1)).profit == ((input)(o2)).profit)
                    return 0;
                else return -1;
            }});
     }

     @SuppressWarnings("unchecked")
     public void sortbydeadline(List<input> datas)
      {
          Collections.sort(datas, new Comparator() {

             public int compare(Object o1, Object o2)
             {
                 if(((input)(o1)).deadline > ((input)(o2)).deadline)
                     return 1;
                 else if(((input)(o1)).deadline == ((input)(o2)).deadline)
                     return 0;
                 else return -1;
             }});
      }


     @SuppressWarnings("unchecked")
     public void sortbySum(List<input> datas)
      {
          Collections.sort(datas, new Comparator() {

             public int compare(Object o1, Object o2)
             {
                 if(((input)(o1)).sum() > ((input)(o2)).sum())
                     return 1;
                 else if(((input)(o1)).sum() == ((input)(o2)).sum())
                     return 0;
                 else return -1;
             }});
      }


    @SuppressWarnings("unchecked")
    public static void main(String[] args)
    {
        tarea tsk = new tarea();
        //tsk.readData1();
        //tsk.readData2();
        tsk.readData3();


        while (tsk.datas.size() > 0)
        {
            //sort by profit
            tsk.sortbyprofit(tsk.datas);
            int idx0 = 1;
            //assign index
            for (input data : tsk.datas)
            {
                data.index1 = idx0;
                idx0++;
            }

            //sort by deadline
            tsk.sortbydeadline(tsk.datas);
            int idx2 = 1;
            for (input data : tsk.datas)
            {
                data.index2 = idx2;
                idx2++;
            }

            //sort by sum and profit
            tsk.sortbySum(tsk.datas);

            List<input> tmpdatas = new ArrayList<input>();
            int valsum = tsk.datas.get(0).sum();
            for (input data : tsk.datas)
            {
                if (data.sum() == valsum)
                    tmpdatas.add(data);
            }            
            tsk.sortbyprofit(tmpdatas);

            //get the first one as result
            input thedata = tmpdatas.get(0);

            System.out.println("result ===> " + thedata.profit);

            tsk.datas.remove(thedata);
            tmpdatas = new ArrayList<input>();
            for (input data : tsk.datas)
            {
                data.deadline--;
                if (data.deadline > 0)
                    tmpdatas.add(data);
            }
            tsk.datas = tmpdatas;
        }


    }


}

Answer 4

Хорошо, Java здесь не проблема. Вместо того, чтобы концентрироваться на языке, подумайте об алгоритме.

Это "на вкус" как что-то, где есть динамическое программирование решения, но из этого я могу сделать вывод, что вы новичок, так что исчерпывающий поиск - это проще, если количество заказов разумно. В исчерпывающем поиске вы просто разместите каждый возможный ордер и сохраните самый прибыльный.