무게로 포장

Question

1 파운드 미만의 품목이 많고이를 1 파운드 컨테이너에 효율적으로 포장하려면 무차별 대로해야합니까? (모든 다양한 조합을 찾아서 포장하고 어떤 조합이 가장 작은 수의 패키지로 연결되는지 확인하십시오.)

알고리즘의 종류에 대한 이름이 있습니까?

필자는 많은 패키지가 없다.

Answer 1

이 문제를 해결하기 위해 다음 Ruby 프로그램을 작성했지만 제대로 작동하는 것 같습니다.

https://gist.github.com/1398026

Answer 2

당신은 또한 1D 빈 포장 또는 2D 빈 - 포장 알고리즘 볼 수 있습니다 knapsack problem

Answer 3

보고 할 수 있습니다. 너무 많은 쓰레기통이 없다면 나는 brute-force 알고리즘을 제안하지만 매우 어려운 문제로 보인다.

Answer 4

NP 완료 문제입니다. 당신은 훨씬 더 나은 옵션을 가지고 있지 않을 것입니다, 아마도 가장 좋은 의사 다중 (지수) 복잡성을 가진 동적 프로그래밍 알고리즘 일 것입니다.

Answer 5

당신은 당신의 문제에 대한 설명은 알고리즘 디자인 매뉴얼로 볼 수

:

빈 http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

배낭 문제를 포장은 http://www.cs.sunysb.edu/~algorith/files/knapsack.shtml

당신은 아마에 쉽게 그것을 만들 수 있습니다 당신이 적당한 솔루션을 정의 할 수 있다면 (충분히 좋다), 당신이 가장 잘 알고 싶다면 해결책.