包裝問題

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。