튜브를 맞춤화할 때 최소 낭비를 계산하는 방법

Question

해결해야 할 다소 수학적 문제가 있습니다.

작업은 최소한의 폐기물을 사용하여 고정 길이 튜브에서 미리 정의된 수의 튜브를 절단하는 것입니다.

그래서 표준화된 길이 6m의 튜브에서 10개의 1m 튜브와 20개의 2,5m 튜브를 자르고 싶다고 가정해 보겠습니다.

이런 종류의 문제에 대한 알고리즘이 어떤 모습일지 잘 모르겠습니다.

나는 다양한 크기의 튜브의 변형 목록을 만들고 표준 크기의 튜브에 맞추고 최소 폐기물의 변화를 선택하려고 생각했습니다.

먼저 문제를 공격하는 다른 더 좋은 방법이 없는지 잘 모르겠습니다.

둘째, 그러한 변형 목록을 만드는 방법에 대한 해결책을 찾지 못했습니다.

어떤 도움이라도 대단히 감사하겠습니다. 감사합니다!

Answer 1

나는 당신이 묘사하고 있다고 믿습니다 재고 문제 절단. 몇 가지 추가 정보를 찾을 수 있습니다 여기.

Answer 2

이는 다음과 같이 알려져 있습니다. 절단재 문제.Wikipedia에는 ​​작동하는 알고리즘에 대한 단서를 찾는 데 도움이 될 수 있는 많은 참고 자료가 있습니다.