분수 배낭 문제: 예제가 있는 탐욕 알고리즘
사라 첸
탐욕스러운 전략이란 무엇입니까?
탐욕 알고리즘은 동적 프로그래밍 알고리즘과 유사하며, 종종 최적 문제(특정 기준에 따라 문제의 가장 좋은 해법을 찾는 것)를 해결하는 데 사용됩니다.
탐욕 알고리즘은 해당 선택이 해결하려는 문제에 대한 최적의 글로벌 솔루션으로 이어질 것이라는 희망으로 최적의 로컬 선택을 구현합니다. 탐욕 알고리즘은 종종 설정하기 어렵지 않고 빠릅니다(시간 복잡도는 종종 선형 함수이거나 2차 함수입니다). 게다가 이러한 프로그램은 디버깅하기 어렵지 않고 메모리를 덜 사용합니다. 하지만 결과가 항상 최적의 솔루션은 아닙니다.
탐욕 전략은 종종 옵션 A를 구축하여 조합 최적화 문제를 해결하는 데 사용됩니다. 옵션 A는 완료될 때까지(충분한 n개의 구성 요소) A의 각 구성 요소 Ai를 선택하여 구성됩니다. 각 Ai에 대해 최적의 Ai를 선택합니다. 이런 방식으로 마지막 단계에서는 마지막 남은 값을 적용하는 것 외에는 선택할 것이 없을 수도 있습니다.
탐욕스러운 결정에는 두 가지 중요한 구성 요소가 있습니다.
- 탐욕적 선택 방식. 현재 가장 좋은 해결책을 선택한 다음 마지막 선택을 한 후 발생하는 하위 문제를 해결할 수 있습니다. 탐욕적 알고리즘의 선택은 이전 선택에 따라 달라질 수 있습니다. 그러나 미래의 선택이나 하위 문제의 솔루션에 따라 달라질 수는 없습니다. 알고리즘은 루프에서 선택을 하는 방식으로 진화하는 동시에 주어진 문제를 더 작은 하위 문제로 축소합니다.
- 최적의 하부 구조. 문제의 최적 솔루션에 해당 하위 문제에 대한 최적 솔루션이 포함된 경우 문제에 대한 최적 하위 구조를 수행합니다.
그리디 알고리즘에는 다섯 가지 구성 요소가 있습니다.
- 솔루션을 생성할 후보 집합입니다.
- 솔루션에 추가할 가장 적합한 후보를 선택하는 선택 기능입니다.
- 실행 가능 함수는 후보가 솔루션을 구축하는 데 사용될 수 있는지 결정하는 데 사용됩니다.
- 해 또는 불완전한 해의 값을 고정하는 목적 함수입니다.
- 완전한 솔루션을 찾은 시기를 나타내는 평가 기능입니다.
욕심 많은 자의 생각
첫 번째 아이디어를 사용하면 Greedy One의 단계는 다음과 같습니다.
- 값이 증가하지 않는 순서로 정렬합니다.
- 차례로 주문한 패키지를 고려하여 배낭의 남은 용량이 배낭에 담을 수 있을 만큼 충분하면 고려 패키지를 배낭에 넣습니다. 즉, 배낭에 넣은 패키지의 총 중량과 고려 패키지의 무게가 초과하지 않음을 의미합니다. 배낭의 용량).
그러나 이 그리디 알고리즘이 항상 최적의 솔루션을 제공하는 것은 아닙니다. 여기에 반대 예가 있습니다.
- 문제의 매개변수는 다음과 같습니다. n = 3; 남 = 19.
- 패키지: {i = 1; W[i] = 14; V[i] = 20}; {나는 = 2; W[i] = 6; V[i] = 16}; {나는 = 3; W[i] = 10; V[i] = 8} -> 가치도 훌륭하지만 무게도 큽니다.
- 알고리즘은 총 값이 1인 패키지 20을 선택하고 총 값이 2인 문제의 최적 솔루션(패키지 3, 패키지 24)을 선택합니다.
탐욕스러운 XNUMX의 아이디어
두 번째 아이디어를 사용하면 Greedy Two의 단계는 다음과 같습니다.
- 가중치가 감소하지 않는 순서로 정렬합니다.
- 차례로 주문한 패키지를 고려하여 배낭의 남은 용량이 배낭에 담을 수 있을 만큼 충분하면 고려 패키지를 배낭에 넣습니다. 즉, 배낭에 넣은 패키지의 총 중량과 고려 패키지의 무게가 초과하지 않음을 의미합니다. 배낭의 용량).
그러나 이 그리디 알고리즘이 항상 최적의 솔루션을 제공하는 것은 아닙니다. 여기에 반대 예가 있습니다.
- 문제의 매개변수는 다음과 같습니다. n = 3; 남 = 11.
- 패키지: {i = 1; W[i] = 5; V[i] = 10}; {나는 = 2; W[i] = 6; V[i] = 16}; {나는 = 3; W[i] = 10; V[i] = 28} -> 무게는 가볍지만 값도 매우 가볍습니다.
- 알고리즘은 총 값이 1인 (패키지 2, 패키지 26)를 선택하는 반면, 문제의 최적 솔루션은 총 값이 3인 (패키지 28)입니다.
욕심 많은 XNUMX인의 생각
세 번째 아이디어로, 당신은 Greedy Three의 다음 단계를 갖게 됩니다. 사실, 이것은 가장 널리 사용되는 알고리즘입니다.
- 단가가 증가하지 않는 순서로 패키지 정렬
. 당신은 가지고 있습니다:
- 차례로 주문한 패키지를 고려하여 배낭의 남은 용량이 배낭에 담을 수 있을 만큼 충분하면 고려 패키지를 배낭에 넣습니다. 즉, 배낭에 넣은 패키지의 총 중량과 고려 패키지의 무게가 초과하지 않음을 의미합니다. 배낭의 용량).
생각: 그 문제의 탐욕스러운 생각은 
각각의 비율 
. 그런 다음 이 비율을 내림차순으로 정렬합니다. 당신은 가장 높은 것을 선택할 것입니다 패키지와 배낭의 용량은 해당 패키지를 담을 수 있습니다(남은 > wi). 배낭에 패키지를 넣을 때마다 배낭의 용량도 줄어듭니다.
패키지 선택 방법:
- 단위 비용의 배열을 고려하십시오. 단위 비용 감소에 따라 패키지를 선택합니다.
- 부분적인 해결책을 찾았다고 가정합니다: (x1,…, Xi).
- 배낭의 가치는 다음과 같습니다.
- 배낭에 넣은 패키지의 무게에 해당:
- 따라서 배낭의 남은 무게 제한은 다음과 같습니다.
알고리즘의 단계
이것이 최대값을 찾는 문제라는 것을 알 수 있습니다. 패키지 목록은 분기를 고려하여 단가 내림차순으로 정렬됩니다.
- 1단계: 노드 루트는 패키지를 선택하지 않은 배낭의 초기 상태를 나타냅니다.
- 총값 = 0.
- 루트 노드의 상한 UpperBound = M * 최대 단위 비용.
- 2단계: 노드 루트에는 단위 비용이 가장 큰 패키지를 선택하는 능력에 해당하는 하위 노드가 있습니다. 각 노드에 대해 매개변수를 다시 계산합니다.
- TotalValue = TotalValue(이전) + 선택한 패키지 수 * 각 패키지의 값.
- M = M(기존) – 선택한 패키지 수 * 각 패키지의 무게.
- UpperBound = TotalValue + M(신규) * 다음에 고려되는 포장의 단가입니다.
- 3단계: 하위 노드에서는 상한이 더 큰 노드에 대한 분기 우선 순위를 지정합니다. 이 노드의 자식은 단위 비용이 큰 다음 패키지를 선택하는 능력에 해당합니다. 각 노드에 대해 2단계에서 언급한 공식에 따라 TotalValue, M, UpperBound 매개변수를 다시 계산해야 합니다.
- 4단계: 참고: 상한이 발견된 옵션의 임시 최대 비용보다 낮거나 같은 값인 노드의 경우 더 이상 해당 노드에 대해 분기할 필요가 없다는 점을 참고하여 3단계를 반복합니다.
- 5단계: 모든 노드가 분기되거나 절단되는 경우 가장 비용이 많이 드는 옵션을 찾아야 합니다.
알고리즘의 의사 코드:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
알고리즘의 복잡성:
- 간단한 정렬 알고리즘(선택, 버블 등)을 사용하는 경우 전체 문제의 복잡도는 O(n2)입니다.
- 퀵 정렬이나 병합 정렬을 사용하는 경우 전체 문제의 복잡도는 O(nlogn)입니다.
Java Greedy Three의 코드
- 먼저 KnapsackPackage 클래스를 정의합니다. 이 클래스에는 각 패키지의 무게, 가치 및 해당 비용과 같은 속성이 있습니다. 이 클래스의 속성 비용은 기본 알고리즘에서 작업을 정렬하는 데 사용됩니다. 각 비용의 가치는
각 패키지의 비율.
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 = new Double(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 kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
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());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
코드 설명:
- 각 배낭 패키지의 무게와 값을 초기화합니다.
- 배낭 패키지를 비용별로 내림차순으로 정렬합니다.
- 패키지를 선택한 경우 i.
- 패키지 수를 선택하면 충분합니다.
- 모든 패키지를 탐색할 때는 중지하세요.
이 튜토리얼에는 두 가지 예가 있습니다. 다음은 두 가지 예와 함께 위 프로그램을 실행하는 Java 코드입니다.
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
출력은 다음과 같습니다.
- 첫 번째 예:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- 두 번째 예:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
첫 번째 예를 분석해 보세요.
- 문제의 매개변수는 다음과 같습니다. n = 4; 남 = 37.
- 패키지: {i = 1; W[i] = 15; V[i] = 30; 비용 = 2.0}; {나는 = 2; W[i] = 10; V[i] = 25; 비용 = 2.5}; {나는 = 3; W[i] = 2; V[i] = 4; 비용 = 1.0}; {나는 = 4; W[i] = 4; V[i] = 6; 비용 = 1.5}.
- 단가 값이 증가하지 않는 순서로 패키지를 정렬합니다. 당신은: {i = 2} -> {나 = 1} -> {나 = 4} -> {나 = 3}.
첫 번째 예에 알고리즘을 적용하는 단계:
- x1, x2, x3을 정의합니다. x4는 패키지 {i = 2}에 해당하는 선택된 각 패키지의 수입니다. -> {나 = 1} -> {나 = 4} -> {나 = 3}.
- 노드 루트 N은 패키지를 선택하지 않은 상태를 나타냅니다. 그 다음에:
- 총값 = 0.
- M = 37(제안대로).
- UpperBound = 37 * 2.5 = 92.5 중 37은 M이고 2.5는 패키지 {i = 2}의 단위 비용입니다.
- 패키지 {i = 2}를 사용하면 4가지 가능성이 있습니다. 3 패키지 {i = 2}(x1 = 3)를 선택합니다. 2개의 패키지 선택 {i = 2} (x1 = 2); 1개의 패키지 {i = 2}(x1 = 1)를 선택하고 패키지 {i = 2}(x1 = 0)를 선택하지 않습니다. 이러한 4가지 가능성에 따라 루트 노드 N을 4개의 하위 N[1], N[2], N[3] 및 N[4]로 분기합니다.
- 하위 노드 N1의 경우 다음이 있습니다.
- TotalValue = 0 + 3 * 25 = 75. 여기서 3은 선택한 패키지 {i = 2}의 수이고 25는 각 패키지 {i = 2}의 값입니다.
- M = 37 – 3 * 10 = 7, 여기서 37은 배낭의 초기 수량, 3은 패키지 수{i = 2}, 10은 각 패키지의 무게{i = 2}입니다.
- UpperBound = 75 + 7 * 2 = 89, 여기서 75는 TotalValue, 7은 배낭의 남은 무게, 2는 패키지의 단가입니다. {i = 1}.
- 마찬가지로 노드 N[2], N[3] 및 N[4]에 대한 매개변수를 계산할 수 있습니다. 여기서 UpperBound는 각각 84, 79 및 74입니다.
- 노드 N[1], N[2], N[3] 및 N[4] 중에서 노드 N[1]이 가장 큰 UpperBound를 가지므로 노드 N[1]을 먼저 분기합니다. 이 방향에서 좋은 계획이군요.
- 노드 N[1]에는 x1 = 1에 해당하는 하위 노드 N[2-0]이 하나만 있습니다(배낭의 나머지 무게는 7이고 각 패키지의 무게 {i = 1}은 15이기 때문입니다). . N[1-1] 버튼에 대한 매개변수를 결정한 후 N[1-1]의 UpperBound는 85.5입니다.
- 노드 N[1-1]을 계속 분기합니다. 노드 N[1-1]에는 x2 = 1 및 x1 = 1에 해당하는 1개의 하위 N[1-2-3] 및 N[1-3-0]이 있습니다. 이 두 노드에 대한 매개변수를 결정한 후 다음을 알 수 있습니다. N[1-1-1]의 UpperBoundary는 84이고 N[1-1-2]의 UpperBoundary는 82이므로 노드 N[1-1-1]을 계속 분기합니다.
- 노드 N[1-1-1]에는 x1 = 1 및 x1 = 1에 해당하는 N[1-1-1-2] 및 N[4-1-4-0]라는 두 개의 하위 노드가 있습니다. 이는 두 개의 리프 노드입니다. (옵션을 나타냄) 각 노드에 대해 패키지 수가 선택되었기 때문입니다. 노드 N[1-1-1-1]은 1에 대해 옵션 x3 = 2, x0 = 3, x1 = 4 및 x1 = 83을 나타내고, 노드 N[1-1-1-2]는 옵션 x1을 나타냅니다. = 3, x2 = 0, x3 = 1 및 x4 = 01(81). 따라서 여기서 임시 최대값은 83입니다.
- 노드 N[1-1-2]로 돌아가면 N[1-1-2]의 UpperBound가 82 < 83이므로 노드 N[1-1-2]를 자릅니다.
- 노드 N2로 돌아가면 N2의 UpperBound가 84 > 83임을 알 수 있으므로 노드 N2를 계속 분기합니다. 노드 N2에는 x2 = 1 및 x2 = 2에 해당하는 두 개의 하위 N[2-1] 및 N[2-0]가 있습니다. N[2-1] 및 N[2-2]에 대한 매개변수를 계산한 후 다음을 볼 수 있습니다. N[2-1]의 UpperBound는 83이고 N[2-2]의 UpperBound는 75.25입니다. 이 값 중 어느 것도 83보다 크지 않으므로 두 노드가 모두 잘립니다.
- 마지막으로 노드 N3과 N4도 잘립니다.
- 따라서 트리의 모든 노드는 분기되거나 잘리므로 가장 좋은 임시 솔루션을 찾아야 합니다. 따라서 3개의 패키지 {i = 2}, 1개의 패키지 {i = 4} 및 3개의 패키지 {i = 83}를 선택해야 하며 총 값은 36이고 총 중량은 XNUMX입니다.
두 번째 예를 동일하게 분석하면 결과가 나옵니다. 패키지 4(3회)와 패키지 5(3회)를 선택합니다.
PythonGreedy Three의 코드 3개
- 먼저 KnapsackPackage 클래스를 정의합니다.
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
- 그런 다음 Greedy Three 알고리즘을 수행하는 함수를 만듭니다.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
코드 설명:
- 각 배낭 패키지의 무게와 값을 초기화합니다.
- 배낭 패키지를 비용별로 내림차순으로 정렬합니다.
- 패키지를 선택한 경우 i.
- 패키지 수를 선택하면 충분합니다.
- 모든 패키지를 탐색할 때는 중지하세요.
여기에 Python첫 번째 예에서 위 프로그램을 실행하는 3개의 코드는 다음과 같습니다.
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)
출력은 다음과 같습니다.
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Greedy Three용 C# 코드
- 먼저 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 = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- 그런 다음 Greedy Three 알고리즘을 수행하는 함수를 만듭니다.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
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, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
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);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
코드 설명:
- 각 배낭 패키지의 무게와 값을 초기화합니다.
- 배낭 패키지를 비용별로 내림차순으로 정렬합니다.
- 패키지를 선택한 경우 i.
- 패키지 수를 선택하면 충분합니다.
- 모든 패키지를 탐색할 때는 중지하세요.
첫 번째 예에서 위 프로그램을 실행하는 C# 코드는 다음과 같습니다.
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
출력은 다음과 같습니다.
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Greedy Three의 반대 사례
Greedy Three의 알고리즘은 신속하게 해결되며 경우에 따라 최적일 수도 있습니다. 그러나 일부 특수한 경우에는 최적의 솔루션을 제공하지 않습니다. 여기에 반대 예가 있습니다.
- 문제의 매개변수는 다음과 같습니다. n = 3; 남 = 10.
- 패키지: {i = 1; W[i] = 7; V[i] = 9; 비용 = 9/7}; {나는 = 2; W[i] = 6; V[i] = 6; 비용 = 1}; {나는 = 3; W[i] = 4; V[i] = 4; 비용 = 1}.
- 알고리즘은 총 값이 1인 (패키지 9)을 선택하는 반면, 문제의 최적 솔루션은 총 값이 2인 (패키지 3, 패키지 10)입니다.
다음은 반례를 사용하여 위 프로그램을 실행하는 Java 코드입니다.
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
결과는 다음과 같습니다.
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
이것이 분수 배낭 문제의 전부입니다.
