분수 배낭 문제: 예제가 있는 탐욕 알고리즘
사라 첸
⚡ 스마트 요약
부분 배낭 문제는 가치 대비 무게 비율에 따라 배낭을 정렬하고 그 순서대로 항목을 선택하는 탐욕 알고리즘을 사용하며, 남은 용량을 항목의 일부로 채울 수 있도록 하여 최적의 해를 보장합니다.
탐욕스러운 전략이란 무엇입니까?
욕심 많은 알고리즘 각 단계에서 최적의 지역적 선택을 통해 일련의 지역 최적해를 도출하여 전역 최적해를 얻는 방식입니다. 동적 프로그래밍과 마찬가지로 최적화 문제를 목표로 하지만, 이전의 결정을 재고하지 않습니다.
탐욕 알고리즘은 일반적으로 작성하기 쉽고, 빠르며(대개 선형 또는 2차 시간 복잡도), 디버깅이 용이하고, 메모리 사용량이 적습니다. 하지만 결과가 항상 최적은 아니므로, 탐욕 알고리즘이 안전한 구조를 가진 문제에만 적용할 수 있다는 단점이 있습니다.
탐욕적 전략은 조합 최적화 문제를 해결하기 위해 구성 요소 Ai를 한 번에 하나씩 구축합니다. 각 단계에서 현재 제약 조건 하에서 Ai를 최적으로 선택하고 문제를 더 작은 하위 문제로 축소합니다.
탐욕적 알고리즘이 올바르려면 두 가지 조건이 충족되어야 합니다.
- 탐욕적 선택 속성: 각 단계에서의 지역 최적점은 전역 최적점으로 이어진다. 선택은 과거의 결정에 따라 달라지지만 미래의 결정에는 영향을 받지 않는다.
- 최적 하위 구조: 전체 문제의 최적해는 하위 문제들의 최적해를 포함한다.
그리디 알고리즘에는 다섯 가지 구성 요소가 있습니다.
- 솔루션을 구축하는 데 사용되는 후보 집합.
- 최적의 차기 후보를 선택하는 함수.
- 후보가 현재의 부분 해를 확장할 수 있는지 여부를 확인하는 타당성 검사 함수입니다.
- 완전한 해와 부분적인 해의 가치를 평가하는 목적 함수.
- 솔루션이 완료되었음을 알리는 평가 함수.
욕심 많은 자의 생각
탐욕스러운 사람은 오직 가격만을 기준으로 패키지를 정렬합니다.
- 패키지를 가격 내림차순으로 정렬하세요.
- 정렬된 목록을 따라 걸으면서 남은 공간에 들어갈 수 있다면 각 물품을 배낭에 넣으세요.
이 규칙이 항상 최적의 해답을 제시하는 것은 아닙니다. 반례:
- 매개변수: n = 3, M = 19.
- 패키지: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — 가치는 높지만 무게도 많이 나갑니다.
- 탐욕스러운 사람은 총 가치가 20인 패키지 1을 선택하지만, 최적의 선택(패키지 2, 패키지 3)은 24에 도달합니다.
탐욕스러운 XNUMX의 아이디어
Greedy Two는 무게만으로 소포를 분류합니다.
- 소포들을 무게가 적은 순서대로 정렬하세요.
- 정렬된 목록을 따라 걸으면서 남은 공간에 들어갈 수 있다면 각 물품을 배낭에 넣으세요.
이 규칙 또한 최적의 규칙이 아닙니다. 반례:
- 매개변수: n = 3, M = 11.
- 패키지: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — 가볍지만 가치가 낮습니다.
- 탐욕스러운 선택은 패키지 1과 패키지 2를 합쳐 총 가치가 26인 반면, 최적의 선택(패키지 3)은 28에 도달합니다.
욕심 많은 XNUMX인의 생각
Greedy Three는 가치와 가중치를 단일 순위 기준으로 결합함으로써 두 가지 실패를 모두 해결합니다. 이는 부분 배낭 문제에 대한 표준 방법입니다.
- 각 패키지에 대한 단위 비용 V[i] / W[i]를 계산합니다.
- 단가가 오름차순으로 정렬하세요.
- 정렬된 목록을 순회하면서 남은 용량에 여유가 있다면 각 패키지를 추가합니다.
단위 비용 V[i] / W[i]에 따른 세 가지 정렬
아이디어 : 모든 패키지에 대해 가치 대 무게 비율 V[i] / W[i]를 계산하고 내림차순으로 정렬한 다음 배낭이 가득 찰 때까지 사용 가능한 가장 큰 비율부터 먼저 가져옵니다.
진실을 위해 분수의 변형 규칙으로, 다음 패키지가 전체를 담을 수 없을 경우, 남은 용량을 정확히 채우는 만큼의 일부를 가져갑니다. 이 추가 규칙 덕분에 Greedy Three는 Fractional Knapsack 문제에서 최적의 알고리즘임이 입증되었습니다.
알고리즘의 단계
0/1 분기 한정법 변형의 경우, 정렬된 단위 비용 목록이 탐색 트리를 생성합니다.
- 1 단계 : 루트 노드는 빈 배낭을 나타냅니다. 총 가치 = 0. 상한 = M × 최대 단위 비용.
- 2 단계 : 루트를 최대 비율 패키지의 복사본이 들어갈 수 있는 개수만큼 분기합니다. 각 자식에 대해 TotalValue, 남은 용량 M 및 UpperBound를 다시 계산합니다.
- 3 단계 : 가장 큰 상한값을 가진 아이부터 먼저 확장하여, 신속하게 강력한 해결책을 찾을 수 있기를 기대합니다.
- 4 단계 : UpperBound가 현재 최상의 완전 해보다 좋지 않은 노드는 모두 제거합니다.
- 5 단계 : 모든 노드를 확장하거나 가지치기하면 현재 가장 완벽한 솔루션이 최적해가 됩니다.
순수 부분 배낭 문제 탐욕 알고리즘의 의사 코드:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size(V) 2. cost[i] <- V[i] / W[i] 3. Sort-Descending(cost) 4. total <- 0 5. i <- 1 6. while (i <= size(V) and M > 0) 7. if W[i] <= M 8. M <- M - W[i] 9. total <- total + V[i] 10. i <- i + 1 11. else 12. total <- total + V[i] * (M / W[i]) 13. M <- 0
알고리즘의 복잡도:
- 단순 정렬(선택 정렬 또는 버블 정렬) 사용 시: O(n)2).
- 퀵 정렬 또는 병합 정렬을 사용하면 시간 복잡도가 O(n log n)이 되며, 정렬 단계가 가장 큰 영향을 미칩니다.
Java Code 탐욕스러운 세 사람을 위해
정의 KnapsackPackage 무게, 가치 및 파생 비용(정렬에 사용되는 V/W 비율)을 기준으로 분류된 클래스:
public class KnapsackPackage { private double weight; private double value; private Double cost; public KnapsackPackage(double weight, double value) { super(); this.weight = weight; this.value = value; this.cost = Double.valueOf(value / weight); } public double getWeight() { return weight; } public double getValue() { return value; } public Double getCost() { return cost; } }
다음으로 Greedy Three를 구현하는 함수를 생성하세요.
public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i++) { packs[i] = new KnapsackPackage(W[i], V[i]); } Arrays.sort(packs, new Comparator<KnapsackPackage>() { @Override public int compare(KnapsackPackage a, KnapsackPackage b) { return b.getCost().compareTo(a.getCost()); } }); double remain = M; double result = 0d; for (int i = 0; i < n && remain > 0; i++) { if (packs[i].getWeight() <= remain) { remain -= packs[i].getWeight(); result += packs[i].getValue(); System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue()); } else { double fraction = remain / packs[i].getWeight(); result += packs[i].getValue() * fraction; System.out.println("Pack " + i + " - Fraction " + fraction + " - Value " + packs[i].getValue() * fraction); remain = 0; } } System.out.println("Max Value:\t" + result); }
knapsackGreProc() 함수 Java
코드 설명:
- 모든 입력값을 감싸세요
KnapsackPackage따라서 정렬 키(V/W 비율)는 미리 계산됩니다. - 비용이 높은 순서대로 내림차순으로 정렬하세요.
- 포장이 들어갈 수 있다면, 각 포장을 통째로 가져가세요.
- 남은 공간을 채우기 위해 다음 포장에서 일부를 덜어내세요.
- 잔여 용량이 0이 되는 즉시 중단하십시오.
수정 사항: 원래 Java 루프 고급 i 패키지가 맞지 않을 때만 동일한 패키지를 반복적으로 가져가는 문제가 있었습니다. 위의 버전은 반복마다 패키지를 하나씩 이동시키고, 부분 채우기 단계를 추가하여 실제 부분 배낭 규칙과 일치하도록 했습니다.
Java 알고리즘을 예제에 적용하여 실행하는 드라이버:
public void run() { int W[] = new int[]{15, 10, 2, 4}; int V[] = new int[]{30, 25, 2, 6}; int M = 37; int n = V.length; knapsackGreProc(W, V, M, n); }
Python3 Code 탐욕스러운 세 사람을 위해
먼저 정의하세요 KnapsackPackage 수업. 그만큼 __lt__ 이 방법은 비용별로 직접 정렬할 수 있게 해줍니다.
class KnapsackPackage(object): """Knapsack Package Data Class""" def __init__(self, weight, value): self.weight = weight self.value = value self.cost = value / weight def __lt__(self, other): return self.cost < other.cost
다음으로 부분 배낭 문제 해결 루틴을 구현하십시오.
class FractionalKnapsack(object): def knapsackGreProc(self, W, V, M, n): packs = [KnapsackPackage(W[i], V[i]) for i in range(n)] packs.sort(reverse=True) remain = M result = 0 for i in range(n): if remain == 0: break if packs[i].weight <= remain: remain -= packs[i].weight result += packs[i].value print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value) else: fraction = remain / packs[i].weight result += packs[i].value * fraction print("Pack", i, "- Fraction", fraction, "- Value", packs[i].value * fraction) remain = 0 print("Max Value:", result)
knapsackGreProc() 함수 Python
수정 사항: 원래 Python 클래스는 빈 값을 정의했습니다. __init__ 몸체가 없는 상태에서, 그것이 들어 올린다 IndentationError위 버전은 빈 생성자가 필요 없으므로 해당 생성자를 제거했습니다.
첫 번째 예제에 알고리즘을 실행하는 드라이버:
if __name__ == "__main__": W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4 proc = FractionalKnapsack() proc.knapsackGreProc(W, V, M, n)
C# Code 탐욕스러운 세 사람을 위해
정의 KnapsackPackage 수업:
using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost; public KnapsackPackage(double weight, double value) { this.weight = weight; this.value = value; this.cost = value / weight; } public double Weight { get { return weight; } } public double Value { get { return value; } } public double Cost { get { return cost; } } } }
부분 채우기 단계를 포함하는 Greedy Three를 구현하세요:
public void KnapsackGreProc(int[] W, int[] V, int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int k = 0; k < n; k++) packs[k] = new KnapsackPackage(W[k], V[k]); Array.Sort<KnapsackPackage>(packs, (a, b) => b.Cost.CompareTo(a.Cost)); double remain = M; double result = 0d; for (int i = 0; i < n && remain > 0; i++) { if (packs[i].Weight <= remain) { remain -= packs[i].Weight; result += packs[i].Value; Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value); } else { double fraction = remain / packs[i].Weight; result += packs[i].Value * fraction; Console.WriteLine("Pack " + i + " - Fraction " + fraction + " - Value " + packs[i].Value * fraction); remain = 0; } } Console.WriteLine("Max Value:\t" + result); }
C#의 함수 KnapsackGreProc()
반례: 0/1 배낭에 대한 탐욕스러운 3
Greedy Three는 Fractional 변형에서 최적이지만, 아이템을 나눌 수 없는 0/1 배낭에서는 더 나은 선택지가 있습니다. 반례:
- 매개변수: n = 3, M = 10.
- 패키지: {i = 1; W = 7; V = 9; 비용 = 9/7}, {i = 2; W = 6; V = 6; 비용 = 1}, {i = 3; W = 4; V = 4; 비용 = 1}.
- 탐욕스러운 세 사람은 총 가치 9를 얻기 위해 패키지 1을 선택하는 반면, 최적의 0/1 선택(패키지 2, 패키지 3)은 10에 도달합니다.
교훈: 분수가 허용되는 경우에만 Greedy Three를 사용하세요. 0/1 변형의 경우, 다음을 사용하세요. 동적 프로그래밍 대신.
부분 배낭 문제의 응용
- 액체, 분말 또는 벌크 화물을 중량별로 분할하여 적재하는 경우.
- 부분 자금 조달이 가능한 투자 옵션 전반에 걸친 포트폴리오 배분.
- 클라우드 대역폭 공유를 통해 트래픽이 링크의 일부만 사용할 수 있습니다.
- 분할 가능한 작업 부하를 사용하는 공유 시간 슬라이스 모델 하에서의 CPU 스케줄링.
- AI 리소스 할당에서 학습 작업은 GPU의 일부만 사용할 수 있습니다.
