백준 12865번 : 평범한 배낭 (C 언어)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

Code:

#include <stdio.h>
#define max(a,b) (a>b)?a:b
 
int dp[101][100001] = { 0, };
int w[101] = { 0, };
int v[101] = { 0, };
 
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &w[i], &v[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (j - w[i]>=0)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d", dp[n][k]);
}

문제 설명

주어진 무게 제한 내에서 최대 가치를 가지도록 배낭을 채우는 "평범한 배낭" 문제를 해결하는 프로그램입니다.

알고리즘 설명

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결하였습니다. 동적 계획법은 작은 부분 문제들의 해를 이용하여 큰 문제의 해를 구하는 알고리즘으로, 중복된 계산을 피하면서 최적해를 구할 수 있습니다.

배낭 문제의 핵심 아이디어는 각 물건을 넣을지 말지를 결정하는 것입니다. 각 물건에 대해 넣을지 말지를 결정하면서 최대 가치를 계산하고, 그 결과를 테이블에 저장하여 중복 계산을 방지합니다.

1. 입력 받기: 주어진 물건의 수(N)와 배낭의 무게 제한(K)을 입력받습니다.
2. 각 물건의 정보 입력 받기: 각 물건의 무게(W)와 가치(V)를 입력받습니다.
3. 동적 계획법을 이용하여 최대 가치 계산:
   • dp[i][j]는 물건 1부터 i까지 고려하고 배낭의 무게가 j일 때의 최대 가치를 나타냅니다.
   • dp[i][j]는 물건 i를 배낭에 넣을지 말지에 따라 최대 가치를 갱신합니다:
     • 만약 물건 i의 무게(W[i])가 배낭의 무게 제한(j)보다 작거나 같으면, 물건 i를 넣을 수 있습니다.
       • 이때 물건 i를 넣는 경우: dp[i][j] = max(dp[i-1][j], dp[i-1][j - W[i]] + V[i])
       • 이때 물건 i를 넣지 않는 경우: dp[i][j] = dp[i-1][j]
     • 물건 i의 무게(W[i])가 배낭의 무게 제한(j)보다 크면 물건 i는 배낭에 넣을 수 없으므로 이전 단계의 최대 가치를 그대로 사용합니다.
4. 최종 결과 출력: dp[N][K]에 배낭에 넣을 수 있는 물건들의 최대 가치가 저장되어 있으므로, 이 값을 출력합니다.