查找算法类

Question

我有家庭作业要找到/创建解决这个问题的算法：

• n -桶数
• k -块的不同颜色的数目
• p_i -第一桶容量
• c_i -具有I色的块数

假设桶是站在圆周上的。

要做的是：

每个水桶必须有最多一个块的每种颜色。基本操作是将块转移到邻桶。

我不期待这个问题的解决方案，现在我想知道这类问题是图还是其他问题。

非常感谢。

编辑:我必须用c++写它。

编辑:问题示例

• 1桶容量5: 1黄色2绿色
• 2桶容量5 :1白色2黄色
• 3桶容量2: 2蓝色
• 4桶容量7: 1绿色

算法必须使每个桶包含最多一个块的每种颜色。

编辑:我的想法

我在考虑搜索树，在那里我将生成所有正确放置块的可能性，但我不知道如何计算这个解决方案中的步骤。另一个想法是从每个不应该在里面的桶块上“清扫”。最后一个想法是从块的角度和“扫描”桶的角度来看待这个问题，其中包括多个颜色块。但是我找不到任何强有力的想法来解决这个问题。

编辑:我的算法

1. 数一数每种颜色的块数。
2. 按降序排序。
3. 对于每种颜色，从数量最多的颜色开始：
   1. 对于每个桶: 1。如果这个桶包含超过1块颜色，请转到2。否则继续。2.试着给邻居的水桶涂上颜色块。如果任何一个邻居没有足够的位置，那就把邻座的水桶换到这个水桶上，然后把颜色块放到这个水桶上。

​

Answer 1

乍一看，我建议使用Doubly-Linked-List数据结构。但是我不知道你要用什么语言来写，我想没有人能进一步帮助你。

例如，您可以创建一个Doubly-Linked-List，并使用myObject类型的成员填充它。

在Java中，myObject将是一个Class。在C中，myObject将是一个Struct，等等。

您希望链接这些对象，以便每个对象都有对其两个邻居的引用。然后，您可以将一个块传递给“邻居”(链接)桶。

虽然创建数据结构的方式在很大程度上取决于语言.

编辑：在一个简单的例子中，您可以创建对象的array (JavaClass、C Struct等)，然后使用n - 1 (左)和n + 1 (右)给邻居块，其中n是数组中的当前桶。