找到一个或多个机器人为框着色的最少天数的算法
Algorithm to find minimum number of days to color boxes by one or more robots
我有 n 个盒子应该是彩色的。每天机器人都可以给一个盒子上色或生成另一个机器人，从第二天开始，他的工作方式与他的 parent 完全相同。
也就是说，如果周日我有一个机器人和 10 个球，那么周一：
有一个机器人，1个彩色盒子和9个无色盒子，或
有 2 个机器人和 10 个未着色的盒子。
我需要找到为所有框着色的最少天数。
我想用动态规划来解决这个问题：
T(n,1) = min(T(n-1,1) + 1, T(n,2))
但我不确定如何创建 DP 矩阵以及 DP 是否是正确的方法。
如 Peter de Rivaz 所述，最佳解决方案是让所有机器人复制直到一天内完成工作，总共需要 1 + ceil(log_2(n)) 天。
你可以写一个动态规划的解决方案，它会工作，但在这里你可以证明这个策略保证最小化天数。
假设有一个最优策略，机器人 r 在第 d 天画了一个盒子。然后，在第 d+2 天之后，机器人 r 前三天的输出将至多为“绘制了 3 个盒子，总共 2 个机器人（包括 r 本身）”或“1 个盒子”画了，总共 4 个机器人。'
如果机器人在喷漆前进行了复制，它在前三天 d+2 天后的输出将是“喷漆 4 个盒子，总共 4 个机器人”，这明显优于替代方案，因此也最佳的。因此您可以得出结论，除非您将在 d 天或 d+1 天之后完成，否则最好在 d.
天进行复制
现在，如果您在 d+1 天后完成了怎么办？在第 d 天复制而不是两天都绘制仍然是最佳选择——无论哪种方式，您都会在两天内绘制两个盒子，这意味着我们的策略至少与任何其他策略一样好。
我有 n 个盒子应该是彩色的。每天机器人都可以给一个盒子上色或生成另一个机器人，从第二天开始，他的工作方式与他的 parent 完全相同。
也就是说，如果周日我有一个机器人和 10 个球，那么周一：
有一个机器人，1个彩色盒子和9个无色盒子，或
有 2 个机器人和 10 个未着色的盒子。
我需要找到为所有框着色的最少天数。
我想用动态规划来解决这个问题：
T(n,1) = min(T(n-1,1) + 1, T(n,2))
但我不确定如何创建 DP 矩阵以及 DP 是否是正确的方法。
如 Peter de Rivaz 所述，最佳解决方案是让所有机器人复制直到一天内完成工作，总共需要 1 + ceil(log_2(n)) 天。
你可以写一个动态规划的解决方案，它会工作，但在这里你可以证明这个策略保证最小化天数。
假设有一个最优策略，机器人 r 在第 d 天画了一个盒子。然后，在第 d+2 天之后，机器人 r 前三天的输出将至多为“绘制了 3 个盒子，总共 2 个机器人（包括 r 本身）”或“1 个盒子”画了，总共 4 个机器人。'
如果机器人在喷漆前进行了复制，它在前三天 d+2 天后的输出将是“喷漆 4 个盒子，总共 4 个机器人”，这明显优于替代方案，因此也最佳的。因此您可以得出结论，除非您将在 d 天或 d+1 天之后完成，否则最好在 d.
现在，如果您在 d+1 天后完成了怎么办？在第 d 天复制而不是两天都绘制仍然是最佳选择——无论哪种方式，您都会在两天内绘制两个盒子，这意味着我们的策略至少与任何其他策略一样好。