배송 크기 조합

Question

배송 할 크기의 제품이 많아서 가장 저렴한 요금을 찾아야합니다.

[1,3,3,5] 크기로 만들어진 선적이 주어지면 배송 방법을 결정해야합니다. 모두 함께 또는 분리해야합니다. 그러나 그것만큼 간단하지 [1,3,3,5] 또는 1 오, 난 같은 가능한 조합 무언가의 모든 필요

[ 
[[1,3,3,5]],   (1 shipment) 
[[1],[3,3,5]],   (2 shipments) 
[[1,3],[3,5]],   (2 shipments) 
[[1,3,3],[5]],   (2 shipments) 
[[1,5],[3,3]],   (2 shipments) 
[[1,3],[3],[5]],  (3 shipments) 
[[1],[3],[3],[5]]  (4 shipments) 
] 

(등 - 많은 난 가정) 를 나는 패싯 젬의 조합을 시도했지만, 내가 겪은 것이 아니며,이 문제에 어떻게 접근해야하는지 잘 모르겠습니다. 나는 이름을 알았을 때 이름과 해결책을 가지고 있을지도 모른다는 것을 이해한다. :)

많은 조합이있을 수 있지만 초기 크기 배열은 7보다 크지 않다는 것을 알고있다.

미리 감사드립니다.

Answer 1

the partitions of a set을 생성하고 싶습니다. 이 Combinatorial Explotion 리드로

Here is very good explanation and working code to do it.

그러나이 일을 아주 좋은 생각이 아니다.

n과 같은 것들은 입니다.

knapsack problem 및 dynamic programming이 문제를 해결하는 올바른 방법이라고 생각합니다.

Answer 2

어쩌면보고 여기 http://en.wikipedia.org/wiki/Packing_problem 여기 http://en.wikipedia.org/wiki/Knapsack_problem이 영감이 될 수 ...

Answer 3

N <= 7를 들어, 당신은 단순히 철저한 될 수 있습니다

비트 마스크와 의사 코드 C 틱에서

:

result =() 
subsets(int x, list current) 
    if (x == 0) 
     result.append(current) 

    for (int i = x; i >= 0; i = ((i - 1) & x)) 
     subsets(x^i, append i to current) 

여기서 "현재에 추가"는 인덱스를 가져 와서 목록에 추가하고 추가하는 것을 의미합니다. 최적화를 가지고 놀고 싶다면 그것을 메모 할 수도 있습니다.

Answer 4

이 문제는 조합 최적화 문헌의 가변 크기 빈 포장 문제로 알려져 있습니다. Bin Packing을 일반화하기 때문에 NP 하드는되지만 브랜치와 바운드와 같은 기법은 너무 무차별 적으로 처리 할 수있는 인스턴스에 대해 합리적인 작업을 수행해야합니다.