탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법으로, 현재 상황에서 가장 좋아보이는 선택을 하며 답을 찾아가는 알고리즘입니다. 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이라고 판단되는 선택을 하는 것이 특징입니다.

탐욕 알고리즘은 대부분의 경우 최적해를 보장하지는 않습니다. 하지만 경우에 따라서는 최적해를 구할 수 있는데, 이를 풀이하는 문제들은 탐욕 알고리즘으로 푸는 것이 바람직합니다. 또한, 탐욕 알고리즘은 다른 알고리즘에 비해서 빠른 속도를 보이기도 합니다.

동작 과정

탐욕 알고리즘의 기본적인 동작 과정은 다음과 같습니다.

1. 해 선택(Selection of solution) : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 해당 부분 문제의 최적해를 전체 문제의 최적해로 합쳐나가는 방식입니다.
2. 실행 가능성 검사(Feasibility check) : 구해진 해가 문제의 조건을 만족하는지 검사합니다.
3. 해 검사(Optimality check) : 구해진 해가 최적인지 검사합니다.

최적해(Optimal solution)

주어진 제약 조건(constraints)에서 가능한 모든 Solution들 중에서, 가장 좋은 Solution를 의미합니다.

구현예시(javascript)

function knapsack(items, capacity) {
  const n = items.length;
  let totalValue = 0;
  let totalWeight = 0;
  
  for (let i = 0; i < n; i++) {
    const [value, weight] = items[i];
    const remainingCapacity = capacity - totalWeight;
    
    if (weight <= remainingCapacity) {
      totalValue += value;
      totalWeight += weight;
    } else {
      const fraction = remainingCapacity / weight;
      totalValue += fraction * value;
      totalWeight += fraction * weight;
      break;
    }
  }
  
  return totalValue.toFixed(2);
}

const items = [
  [60, 10],
  [100, 20],
  [120, 30]
];
const capacity = 50;
console.log(knapsack(items, capacity)); // Output: 240.00

장단점