Programming_question 关于动态规划

Question

一家公司生产一种产品。生产以一种非常神秘的方式进行。该公司要么在一天内多生产一种产品，要么他们有能力将前一天的产品产量翻一番。最初他们只有 1 种产品，但有一天他们正好有 "n" 种产品。您需要找出最少天数才能准确地制作出 "n" 件产品。测试用例： n = 8 输出 = 3 解释：如果每天产量翻倍，则三天内可以生产 1 x 2 x 2 x 2 = 8 件产品。再多一点：对于 15 个产品输出 6 对于 19 个产品输出 6

Answer 1

你需要使用动态规划来解决这个问题。对于给定的 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，最后显示该值。

Programming_question 关于动态规划

Programming_question on dynamic programming

algorithm

dynamic-programming

greedy