포장 알고리즘… 종류

Question

배열이 주어지면 각각은 value 그리고 cost, 최저 비용으로 최소 값에 도달하는 데 필요한 항목을 결정하는 최상의 알고리즘은 무엇입니까? 예 :

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

끝의 전체 값 : 비용 비율은 관련이 없습니다 (A + A 돈을위한 최고의 가치를 줄 것이지만 A + B + B 최소 값에 맞는 저렴한 옵션입니다).

Answer 1

이것은 배낭 문제입니다. (즉,이 문제의 결정 버전은 배낭 문제의 결정 버전과 동일하지만, 매듭 문제의 최적화 버전은 일반적으로 다르게 언급되어 있습니다.) NP-HARD입니다 (이는 알고리즘이 알려져 있지 않음을 의미합니다. "크기"의 다항식 - 입력의 비트 수 - 비트 수). 그러나 숫자가 작다면 (입력에서 가장 큰 "값"이라면, 비용은 중요하지 않다면) 간단한 동적 프로그래밍 솔루션이 있습니다.

최상의 [v]는 (정확히) v의 값을 얻는 데 최소 비용이되도록하자.

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

그런 다음 원하는 최소값과 가장 큰 값에 대한 값에 대해서는 최상의 [v]를 살펴보십시오. 가장 작은 사람들은 당신에게 비용을 줄 것입니다.

실제 항목을 원한다면 (최소 비용뿐만 아니라) 추가 데이터를 유지하거나 최상의 배열을 살펴보고이를 추론 할 수 있습니다.

Answer 2

이 문제는 정수 선형 프로그래밍이라고합니다. NP-HARD입니다. 그러나 예와 같은 작은 문제의 경우 구매 선택의 모든 낮은 조합을 무력화하기 위해 빠른 몇 줄의 코드를 만드는 것은 사소한 일입니다.

NP-Harddoes는 불가능하거나 비싸다는 의미는 아니며, 이는 더 큰 규모의 문제로 해결하기 위해 문제가 빠르게 느려집니다. 3 개의 항목 만 있으면 단순한 마이크로 초로 해결할 수 있습니다.

일반적으로 가장 좋은 알고리즘이 무엇인지에 대한 정확한 질문은 전체 교과서가 있습니다. 좋은 시작은 좋은 오래된 위키 백과.

Answer 3

이 답변 편집이 답변은 사실적으로 부정확하기 때문에 수정됩니다. 이에 대한 조언을 따르는 것은 당신에게 해를 끼칠뿐입니다.

일부 컨테이너의 공간이있는 것보다 더 많은 품목을 포장 할 수 없다고 가정하기 때문에 실제로는 배낭 문제가 아닙니다. 귀하는 공간을 채우는 가장 저렴한 조합을 찾아 오버플로가 발생할 수 있다는 사실이 가능합니다.

내가 알지 못하는 내 솔루션은 최적이지만 매우 가까워 야합니다. 각 항목에 대해 비용 혜택 비율을 계산하고 비용이 혜택이 가장 높은 항목을 찾고이 항목으로 구조를 채우는 것입니다. 하나가 더 항목을위한 공간. 그런 다음 가장 저렴한 품목 중 하나의 비용보다 적은 비용으로 사용 가능한 슬롯을 채울 수있는 다른 사용 가능한 항목과의 조합이 있는지 확인하고 그러한 솔루션이 존재하는 경우 해당 조합을 사용하여 하나 더 사용하십시오. 가장 저렴한 품목의.

수정상 이것은 실제로 NP- 완료 일 수도 있지만 아직 확실하지 않습니다. 어쨌든 모든 실제 목적을 위해이 변형은 순진한 솔루션보다 훨씬 빠르야합니다.