用一个或多个机器人为方框找出最少天数的算法

Question

我有应该着色的n盒。每一天，机器人都可以给一个盒子上颜色，或者生成另一个机器人，从第二天开始，机器人就像他的父母一样工作。

也就是说，如果星期天我有一个机器人和10个球，那么星期一：

1. 有一个机器人，一个彩色盒子和9个未着色的盒子，或者

1. 有2个机器人和10个未着色的盒子。

我需要找到最少的天数来着色所有的盒子。

我想用动态规划来解决这个问题：

T(n,1) = min(T(n-1,1) + 1, T(n,2))

但我不知道如何创建一个DP矩阵，以及DP是否是正确的方法。

Answer 1

正如Peter de Rivaz所指出的，一个最佳的解决方案是让所有的机器人复制到一天内完成任务，总共需要1 + ceil(log_2(n))天数。

您可以编写一个动态编程解决方案，它可以工作，但在这里，您可以展示这种策略可以保证将天数降到最低。

假设有一个最优策略，机器人r在d日绘制一个盒子。然后，在d+2一天之后，机器人r前三天的输出最多为'3盒油漆，2个机器人总数(算上r本身)‘或'1盒油漆，4个总装机器人。’

如果机器人在绘画前进行复制，那么它从前三天开始的d+2输出将是“4盒涂漆，4台总机器人”，这是严格优于其他方案的，因此也是最优的。因此，您可以得出结论，除非在day d或day d+1之后完成，否则在d上进行复制总是最优的。

那么，如果你在第二天之后完成了d+1呢？在d上复制仍然是最好的方法，而不是同时画两天--你可以在两天内画两个盒子，这意味着我们的策略至少和任何其他策略一样好。