DAA-분수 배낭
Greedy 알고리즘은 Knapsack 문제라고하는 잘 알려진 문제로 잘 이해 될 수 있습니다. 다른 알고리즘 접근 방식을 사용하여 동일한 문제를 해결할 수 있지만 Greedy 접근 방식은 Fractional Knapsack 문제를 적절한 시간에 합리적으로 해결합니다. 배낭 문제에 대해 자세히 논의하겠습니다.
배낭 문제
각각 가중치와 값이있는 항목 집합이 주어지면 총 가중치가 주어진 제한보다 작거나 같고 총 값이 가능한 한 커지도록 컬렉션에 포함 할 항목의 하위 집합을 결정합니다.
배낭 문제는 조합 최적화 문제에 있습니다. 실제 문제의 더 복잡한 수학적 모델에서 하위 문제로 나타납니다. 어려운 문제에 대한 일반적인 접근 방식 중 하나는 가장 제한적인 제약 조건을 식별하고 다른 제약 조건을 무시하고 배낭 문제를 해결하고 무시 된 제약 조건을 충족하도록 솔루션을 조정하는 것입니다.
응용
일부 제약과 함께 리소스 할당의 많은 경우에서 문제는 Knapsack 문제와 유사한 방식으로 파생 될 수 있습니다. 다음은 일련의 예입니다.
- 원자재 절단을위한 최소한의 낭비 방법 찾기
- 포트폴리오 최적화
- 재고 문제 절단
문제 시나리오
도둑이 상점을 강탈하고 있으며 W그의 배낭에. 상점에 n 개의 아이템이 있으며 무게는ith 항목은 wi 그리고 그 이익은 pi. 도둑은 어떤 물건을 가져 가야합니까?
이러한 맥락에서 항목은 도둑이 최대 이익을 얻을 수있는 항목을 운반 할 수있는 방식으로 선택되어야합니다. 따라서 도둑의 목적은 이익을 극대화하는 것입니다.
항목의 특성에 따라 배낭 문제는 다음과 같이 분류됩니다.
- 분수 배낭
- Knapsack
분수 배낭
이 경우 항목을 더 작은 조각으로 나눌 수 있으므로 도둑이 항목의 일부를 선택할 수 있습니다.
문제 진술에 따르면
있습니다 n 상점의 항목
무게 ith 항목 $ w_ {i}> 0 $
이익 ith 항목 $ p_ {i}> 0 $ 및
배낭의 용량은 W
이 버전의 배낭 문제에서는 항목을 더 작은 조각으로 나눌 수 있습니다. 그래서 도둑은xi 의 ith 안건.
$$ 0 \ leqslant x_ {i} \ leqslant 1 $$
그만큼 ith 아이템은 배낭의 총 무게에 대한 가중치 $ x_ {i} .w_ {i} $를 기여하고 총 수익에 대한 수익 $ x_ {i} .p_ {i} $를 제공합니다.
따라서이 알고리즘의 목적은
$$ maximize \ : \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .p _ {} i) $$
제약에 따라
$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$
최적의 솔루션이 배낭을 정확하게 채워야한다는 것은 분명합니다. 그렇지 않으면 나머지 항목 중 하나의 일부를 추가하고 전체 수익을 늘릴 수 있습니다.
따라서 최적의 솔루션은 다음과 같이 얻을 수 있습니다.
$$ \ displaystyle \ sum \ limits_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$
이 컨텍스트에서 먼저 $ \ frac {p_ {i}} {w_ {i}} $의 값에 따라 해당 항목을 정렬해야합니다. 따라서 $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $ 여기,x 항목의 일부를 저장하는 배열입니다.
Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for i = 1 to n
do x[i] = 0
weight = 0
for i = 1 to n
if weight + w[i] ≤ W then
x[i] = 1
weight = weight + w[i]
else
x[i] = (W - weight) / w[i]
weight = W
break
return x분석
제공된 항목이 이미 $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $의 내림차순으로 정렬 된 경우 whileloop는 O(n); 따라서 정렬을 포함한 총 시간은O(n logn).
예
배낭의 용량이 W = 60 제공된 항목 목록은 다음 표에 나와 있습니다.
| 안건 | ㅏ | 비 | 씨 | 디 |
|---|---|---|---|---|
| 이익 | 280 | 100 | 120 | 120 |
| 무게 | 40 | 10 | 20 | 24 |
| 비율 $ (\ frac {p_ {i}} {w_ {i}}) $ | 7 | 10 | 6 | 5 |
제공된 항목은 $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $를 기준으로 정렬되지 않습니다. 정렬 후 항목은 다음 표와 같습니다.
| 안건 | 비 | ㅏ | 씨 | 디 |
|---|---|---|---|---|
| 이익 | 100 | 280 | 120 | 120 |
| 무게 | 10 | 40 | 20 | 24 |
| 비율 $ (\ frac {p_ {i}} {w_ {i}}) $ | 10 | 7 | 6 | 5 |
해결책
$ \ frac {p_ {i}} {w_ {i}} $에 따라 모든 항목을 정렬 한 후. 먼저 모든B 무게로 선택됩니다 B배낭의 용량보다 적습니다. 다음으로 항목A 배낭의 사용 가능한 용량이 무게보다 크므로 선택됩니다. A. 지금,C다음 항목으로 선택됩니다. 단, 배낭의 남은 용량이 무게보다 적어 전체 품목을 선택할 수 없습니다.C.
따라서 C (예 : (60-50) / 20)이 선택됩니다.
이제 배낭의 용량은 선택한 항목과 동일합니다. 따라서 더 이상 항목을 선택할 수 없습니다.
선택한 항목의 총 무게는 10 + 40 + 20 * (10/20) = 60
그리고 총 이익은 100 + 280 + 120 * (10/20) = 380 + 60 = 440
이것이 최적의 솔루션입니다. 다른 조합의 항목을 선택하면 더 많은 이익을 얻을 수 없습니다.