Programming_question по динамическому программированию - PullRequest
Новая
       31

Programming_question по динамическому программированию

0 голосов
/ 03 марта 2019

Компания производит продукт.Производство сделано очень таинственным способом.Фирма либо производит один дополнительный продукт в день, либо имеет возможность удвоить производство продуктов, которые они имели в предыдущий день.Первоначально у них есть только 1 продукт, а через некоторое время у них есть ровно «n» продуктов.Вам нужно выяснить минимальные дни, чтобы сделать ровно «n» продуктов.ПРИМЕР: n = 8 выпуск = 3 объяснения: если производство удваивается каждый день, то через три дня можно изготовить 1 x 2 x 2 x 2 = 8 продуктов.Еще немного: Для 15 продуктов ВЫХОД 6 Для 19 продуктов ВЫХОД 6

1 Ответ

0 голосов
/ 06 марта 2019

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

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int main()
{

   int n = -1, i =0, tmp=0;
   // int result = -1;
   printf("\nEnter value: ");
   scanf("%d", &n);

   if (n == -1)
    return -1;


   if(n == 1)
   {
    printf("\nOnly a single day");
    return 0;
   }


   int *arr = malloc(n*sizeof(int));

   for (i=0; i<n; i++)
    arr[i]=INT_MAX;


   arr[0] = 1;

   for(i=1; i<n; i++)
   {
    arr[i] = arr[i-1] + 1;

    if ((i+1)%2 == 0)
    {
        tmp = arr[(i+1)/2 - 1] + 1;
        if (tmp < arr[i])
            arr[i] = tmp;
    }

   }

   printf("\nResult: %d", arr[n-1]-1);
}

Вывод:

Контрольный пример 1: 

Enter value: 8

Result: 3

Контрольный пример 2: 

Enter value: 15

Result: 6

Контрольный пример 3: 

Enter value: 19

Result: 6

КОД ОБЪЯСНЕНИЕ:

Вам нужно создать массив, содержащий столько элементов, сколько это значение.Например,если значение равно 8, вам нужно создать массив из 8 элементов.Затем вам нужно разобраться со значением от 2,3,4 .... до 8. Нет необходимости в значении 1, поскольку, когда вы начинаете, проблема говорит о том, что у вас уже есть 1.Значение в элементах массива обозначает количество дней.Индекс массива таков, что index = value -1.

Ваша конечная цель - добраться до 8.Но вам нужно начать снизу вверх.Вам нужно спросить себя, что вы можете сделать лучше всего (минимальное количество дней) со значением 2?Это либо значение предыдущего элемента +1 (поскольку в задаче указано, что вы либо делаете day's value = previous day's value + 1), либо лучшее, что вы делали со значением, равным половине текущего значения плюс 1 (в задаче указано, что вы можете умножить также на 2в другой раз).Какое бы число ни было меньше, вы назначаете его индексу текущего значения.Эта логика находится внутри цикла for для каждого индекса.

Вы повторяете шаги для 3,4, .... до 8. Теперь, когда вы достигнете 8, значение индекса (8-1) содержат дни, включая начало, поэтому необходимо вычесть 1 и, наконец, отобразить значение.

...