문제

우리는 금속 제품 공장에 대해 이야기하고 있습니다.긴 철봉을 작은 부품으로 절단하여 나중에 다양한 제품을 만드는 데 사용되는 기계가 있습니다.

예를 들어, 다음과 같은 길이와 수량의 막대를 생산해야 한다는 요구 사항이 있습니다.248mm, 1150mm의 5 개, 2843mm의 6 개, 3621mm의 3 개.

이것이 파티셔닝 출력입니다.

입력 측면에는 2500mm의 3 바, 5000mm 2 바, 8000mm의 6 바, 10000mm의 3 바가 있습니다.

입력바를 최적으로 자르는 방법을 찾아야 합니다. 자르고 난 후의 나머지 부분(너무 작아서 사용할 수 없는 나머지 부분)은 가능한 한 작아야 합니다.

나는 가능한 모든 조합을 생성한 다음 그 중에서 가장 좋은 조합을 선택하는 알고리즘을 만들었습니다.코드는 작동하지만 입력과 출력이 조금 더 커지면 계산이 매우 오래 지속될 수 있으므로 문제에 대한 새로운 접근 방식을 찾아야 합니다.

힌트가 있나요?

도움이 되었습니까?

해결책

귀하의 문제는 운영 연구에서 매우 일반적인 문제입니다. 보다재고 문제 절단. 이 문제는 본질적으로 당신이 스스로 알아 낸 것처럼 NP- 하드입니다. 확장되지 않습니다.

그것을 해결하는 방법? 모델을 알아낼 수 있으면 혼합 정수 프로그래밍 솔버를 호출하는 것이 가장 좋습니다. 나는 이전에 사용했습니다 lpsolve 5.5

특히이 문제를 다루는 코딩 할 수있는 단순한 알고리즘이있을 수 있습니다. 이러한 알고리즘의 문제는 일반적으로 저자가 생각하지 않은 측면 제약을 추가해야 할 때 발생합니다. MIP 솔버는보다 일반적인 도구입니다.

다른 팁

이것을 가변 크기 빈 포장 문제. NP 하드이므로 솔루션이 큰 입력에 대해 항상 실패합니다. 이 기사, 여기, 불행히도 나도 접근 할 수 없고이 문제를 해결하고 금속 절단 산업을 예로 사용합니다.

배낭 문제와 유사한 것 같습니다(정말 불쾌한 일이라는 것을 알고 있음). NIST DADS(간편한 참조)에서 비회원의 경우 ACM보다 접근하기가 더 쉽다는 것을 알았습니다. 빈 포장

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top