[알고리즘 문제 풀기] 평범한 배낭(12865)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하여 배낭의 최대 무게까지 각 아이템을 고려하며 최대 가치를 갱신하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int k = int.Parse(split[1]);
    int[] w = new int[n];
    int[] v = new int[n];
    for (int i = 0; i < n; i++)
    {
        split = sr.ReadLine().Split();
        w[i] = int.Parse(split[0]);
        v[i] = int.Parse(split[1]);
    }
    int[] dp = new int[k + 1];
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        if (w[i] > k) continue;
        for (int j = k; j >= w[i]; j--)
        {
            dp[j] = Math.Max(dp[j], dp[j - w[i]] + v[i]);
            result = Math.Max(result, dp[j]);
        }
    }
    sw.WriteLine(result);
}

3. 정리

• dp[j]는 무게 j까지 채울 수 있는 최대 가치를 저장한다.

• 아이템을 하나씩 확인하며 무게를 초과하지 않는 범위 내에서 DP 값을 갱신한다.

• 최대 금액을 갱신했을 때 배낭에 담을 수 있는 최대 가치가 된다.