0/1 Knapsack 문제 이해 및 동적 프로그래밍을 사용한 C# 구현

안녕하세요! 오늘의 기술 면접 지식은 동적 프로그래밍 알고리즘 중 하나인 0/1 Knapsack 문제에 관한 것입니다. 이 포스팅에서는 0/1 Knapsack 문제의 기본 개념과 C#으로 구현한 예제 코드를 살펴봅니다.

0/1 Knapsack 문제 개요

0/1 Knapsack 문제는 배낭에 넣을 수 있는 물건들의 가치의 합을 최대로 하는 조합을 찾는 문제입니다. 각 물건은 무게와 가치를 가지며, 배낭은 일정한 무게의 물건만 담을 수 있습니다. 물건은 쪼갤 수 없으며, 전체 물건을 넣거나 아예 배낭에 넣지 않는 선택만 가능합니다.

C#을 사용한 0/1 Knapsack 문제 구현

아래 예제 코드는 동적 프로그래밍을 사용한 0/1 Knapsack 문제를 C#으로 구현한 것입니다.

 

public static int Knapsack(int[] values, int[] weights, int capacity)
{
    int n = values.Length;
    int[,] dp = new int[n + 1, capacity + 1];

    for (int i = 1; i <= n; i++)
    {
        for (int w = 1; w <= capacity; w++)
        {
            if (weights[i - 1] <= w)
            {
                dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
            }
            else
            {
                dp[i, w] = dp[i - 1, w];
            }
        }
    }

    return dp[n, capacity];
}

 

이 코드는 주어진 물건들의 무게와 가치, 배낭의 용량을 입력으로 받아 최대 가치를 반환합니다. 동적 프로그래밍 테이블을 사용하여 물건들의 조합을 순회하며 최대 가치를 찾습니다.

 

0/1 Knapsack 문제는 동적 프로그래밍 알고리즘 중 하나로, 기술 면접에서 종종 이와 관련된 질문이 나옵니다. 이 포스팅에서 소개한 개념과 구현 예시를 참 고하여 면접에서 확실한 답변을 준비할 수 있습니다. 다음 포스팅에서 또 다른 주제로 찾아뵙겠습니다!