포장 문제

Question

나는 다음과 같은 문제가 있습니다

1. 을 나는이 다른 색상으로 동일하게 형성 항목의 주어진 수의 (I 각 색상에서 얼마나 많은 알고)
2. 나는 상자에 이러한 항목을 포장하는 round_up (total_nr_of_items/n)
3. 일부 색상이 있습니다. 상자에 넣을 수없는 경우를 제외하고는 상자 하나에 넣을 수 없습니다. 그렇지 않으면 이상적인 상자 수를가집니다.
4. 상자에 넣을 수있는 각 색상의 항목이 최소한으로 (각 색상마다 다름) 있습니다. 즉 0 개를 넣을 수 있습니다. 상자에 색을 넣거나 최소 kpcs. 이상. 최소 포장 상자로 포장 할 수없는 경우에도이 제약 조건을 해할 수 있습니다 (가능한 한 몇 번).
5. 상자 사이에 가능한 한 적은 색상이 나뉘는 해결책을 찾고 싶습니다.

필자는 이것이 포장 문제라고 생각하지만 어떤 것이 있는지 모른다.

위의 사항을 위의 문제로 해결할 수있는 포장 문제 및/또는이 문제를 해결하는 데 사용할 수있는 알고리즘을 제안하십시오.

Answer 1

NP-Hard 제한 만족 문제처럼 보입니다. 너는 이렇게 열심히하고 부드러운 제약을 가질 것이다.

축하에서 제약 :

• I이 다른 색상으로 동일하게 형성 항목의 주어진 수의 (I 각 색상에서 얼마나 많은 알고)

하드 제약 :

• 하나의 상자에 넣을 수없는 몇 가지 색상이 있습니다.

• 상자에 넣을 수있는 각 색상의 항목이 각기 다른 최소한의 항목이 있습니다 (각 색상마다 다름). 즉 0 개를 넣을 수 있습니다. 상자에 색을 넣거나 최소 kpcs. 이상.

소프트 제약 : ROUND_UP (total_nr_of_items/:

• 나는 상자의 최소 수를 사용하는 등의 방법으로 각 항목 주어진 수 (N)를 저장할 수있는 상자에 이러한 항목을 팩 n)은

부드러운 제약 (또는 정말 낮은 무게 소프트 제약) :

• 내가 원하는 가능한 한 적은 색상을 상자간에 분할하는 솔루션을 찾습니다.

알고리즘이 문제를 해결하려면, 시뮬레이션 어닐링, 금기 검색, 분기 및 결합, 좀 봐 ... 같은 알고리즘과 지원 제한을 구현하는 소프트웨어에 대한

취할 보기 Drools Planner (자바, 오픈 소스).

Answer 2

NP 하드 일 수 있습니다.

파티션 문제 (양의 정수의 경우)가 줄어들 것 같습니다.

우리가 어떤 부분 집합을 찾을 필요가있는 양의 정수 A [1, ... n]의 배열이 그것의 보수와 같은 합계를 가지면.

1에서 n까지 색상을 고려하십시오. 두 개의 상자가 있습니다. 상자는 색상 i에 대해 가질 수있는 최소값은 A [i]이고 색상 i의 항목은 정확히 A [i]입니다.

각 상자에 저장할 수있는 최대 항목 수는 (A [1] + .. + A [n])/2입니다.