我正在编写一个处理平铺图像的工具。一个功能是将整个图像转换为图块集和瓦片地图，例如，160x144px 的图像将具有一组唯一的 8x8 图块和 20x18 的图块 ID 地图。
下一个目标是支持调色板。在一些使用平铺图形的旧平台上，您可能有 8 个调色板，每个调色板 4 种颜色，或者每个调色板 16 种中的 16 种。我想使用尽可能少的调色板自动创建一组适合 N-by-K 限制的调色板;并将这些调色板分配给磁贴地图，或者在不可能时发出警报。
有一些明显的第一步：如果任何单个磁贴使用超过 K 种颜色，那是不可能的;一旦检查完毕，任何颜色是另一个颜色子集的磁贴都可以轻松共享其调色板。困难在于处理部分重叠的调色板。考虑 17 个图块，每个图块有 15 种独特的颜色;如果有足够的重叠，它们可以适合 16x16 调色板，但可能是不可能的。
我希望动态编程解决方案可以在这里工作。在问题的任何阶段，人们都会将瓷砖部分分配给调色板;并决定将下一个磁贴分配给 N 个调色板中的哪一个。(磁贴甚至可能与当时的最佳调色板选择没有任何共同的颜色;考虑 4 个磁贴，每个磁贴有 4 种独特的颜色，它们都可以使用一个 16 调色板。
这个特殊问题已经解决了吗？是否有已知的算法，或者只是所有动态编程的一般技巧？
SuperFamiconv能够为一些系统做到这一点，包括SNES(16个调色板，8种颜色/调色板(和GBC(8个调色板，4种颜色/调色板(。它也是开源的，所以他们的算法是可用的。
事实证明，动态编程对于给定逼真大小的图像的"足够好"的解决方案不是必需的。(不确定它对大型的有多好，但这对我的目的并不重要。
这是他们的算法到Python的翻译：
def optimize_palettes(tilepals, N, K):
"""
Return an optimized palette set for the given tile set.
tilepals -- A list of sets of unique colors used for each tile of the image
N -- The maximum number of palettes for one image
K -- The maximum number of colors for one tile palette
"""
# Check that each tilepal fits within the color limit
if any(len(s) > K for s in tilepals):
raise OverflowError, "A tile has more than %d unique colors" % K
# Remove duplicate tilepals
sets = []
for s in tilepals:
if s not in sets:
sets.append(s)
# Remove tilepals that are proper subsets of other tilepals
sets = [s for s in sets if not any(c != s and s.issubset(c) for c in sets)]
# Sort tilepals from most to fewest colors
sets.sort(key=len, reverse=True)
# Combine tilepals as long as they fit within the color limit
opt = []
for s in sets:
for cs in opt:
if len(s | cs) <= K:
cs.update(s)
break
else:
opt.append(s)
# Sort tilepals from most to fewest colors
opt.sort(key=len, reverse=True)
# Check that the palettes fit within the palette limit
if len(opt) > N:
raise OverflowError, "There are more than %d palettes" % N
return opt