包装问题

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）

较软约束（或相当低的重量软约束）：

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

对于算法来解决这个问题，看看模拟退火，禁忌搜索，分公司和约束 ...

对于它实现这样的算法和支持软件的限制，采取看看Drools Planner（java，开源）。

Answer 2

这可能是NP-Hard。

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

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

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

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