algorithm - 包装问题

Question

我有以下问题：

1. 我有给定数量的具有不同颜色的相同形状的物品（我知道每种颜色有多少）
2. 我将这些物品打包到可以容纳每个给定数量 (n) 物品的盒子中，这样我就可以使用最少数量的盒子：round_up(total_nr_of_items/n)
3. 有些颜色我不允许放在一个盒子里，除非我不能拥有理想数量的盒子。
4. 我被允许放入盒子中的每种颜色的物品数量最少（每种颜色不同）。那就是我可以决定放 0 件。将一种颜色装入一个盒子或至少 k 个。或以上。如果包装不能用最少数量的盒子完成，这个约束也可以被打破（尽可能少）。
5. 我想找到一个解决方案，在盒子之间拆分尽可能少的颜色。

我认为这是一种包装问题，但我不知道是哪一种。

请建议可以将上述内容转换为哪个打包问题和/或我可以用来解决此问题的算法。

Answer 1

看起来像一个 NP-Hard约束满足问题。你会有像这样的硬约束和软约束。

内置约束：

• 我有给定数量的具有不同颜色的相同形状的物品（我知道每种颜色有多少）

硬约束：

• 有些颜色我不允许放在一个盒子里。

• 我被允许放入盒子中的每种颜色的物品数量最少（每种颜色不同）。那就是我可以决定放 0 件。将一种颜色装入一个盒子或至少 k 个。或以上。

软约束：

• 我将这些物品打包到可以容纳每个给定数量 (n) 物品的盒子中，这样我就可以使用最少数量的盒子：round_up(total_nr_of_items/n)

更软的约束（或真正低权重的软约束）：

• 我想找到一个解决方案，在盒子之间拆分尽可能少的颜色。

有关解决此问题的算法，请查看Simulated annealing、Tabu search、Branch and bound，...

对于实现此类算法并支持约束的软件，请查看Drools Planner（java，开源）。

Answer 2

这可能是 NP-Hard。

分区问题（对于正整数）似乎减少了。

给定一个正整数数组 A[1,...n]，我们需要找到其中的某个子集与它的补码具有相同的和。

考虑你的颜色是 1 到 n。你有两个盒子。一个盒子可以容纳的颜色 i 的最小值是 A[i] 并且你正好有 A[i] 个颜色 i 的项目。

每个盒子可以容纳的最大项目数是 (A[1] + .. + A[n])/2。