dynamic-programming - 如何将具有给定流行度的 n 个元素分配到 k 个通道中（动态规划）

Question

我已经尝试了 2 天，但我被卡住了。

我有一个基站问题，基本上我需要在 k 个不同的信道中分配 n 个元素，从这些信道中，这些元素以循环方式传输。

每个元素都有一个流行度p。高人气意味着它需要更频繁地传播。我们将下载速度定义为 p * w，其中 w = 总 n。通道上的元素数 / 2。问题的目标是使每个通道的通道上的每个元素的总和 Σ(p*w) 尽可能小。

*很明显，必须将流行元素分配给具有少量元素的频道，以便以更高的频率传输它们。但是在同一个频道中分配很多不受欢迎的元素也会增加总和。所以有一个权衡。

前两个问题是：这个问题是否有一个最优的子结构？是否有任何重叠的问题？

这使我相信它需要解决动态编程，但是我无法提出解决方案。

有任何想法吗？提前致谢

标签： dynamic-programminggreedyround-robin