백준 12865번: 평범한 배낭 / C

문제:

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

 

1. DP 방식으로 배낭 문제(Knapsack Problem)를 해결했다.

2. 각 물건에 대해 최대 무게부터 역순으로 탐색하며, 해당 무게에서의 최대 가치를 갱신한다.

3. 모든 물건을 고려한 후, 최대 무게에서의 최대 가치(dp[maxweight])를 출력한다.

 

이 문제는 동적 계획법(DP, Dynamic Programming)을 활용하여 해결할 수 있는 문제이다.

 

DP(Dynamic Programming, 동적 계획법)는 하위 문제의 정답을 저장해두고, 그것을 바탕으로 상위 문제의 정답을 효율적으로 계산하는 방법이다. 보통 배열을 이용해 중간 결과를 저장하며, 중복 계산을 방지한다.

이번 문제에서는 배낭에 담을 수 있는 최대 무게를 기준으로, 각 무게에서 얻을 수 있는 최대 가치를 저장하는 dp 배열을 사용하였다.
아이템을 하나씩 확인하며, 현재 아이템을 넣지 않은 경우와 넣은 경우 중 더 큰 가치를 선택하도록 구현하였다.
이때, 같은 아이템이 여러 번 사용되지 않도록 무게를 역순으로 갱신하였다.

#include <stdio.h>
#include <stdlib.h>

// 두 정수 중 최대값을 반환하는 함수
int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int N, maxweight;
    scanf("%d %d", &N, &maxweight);

    int *W = (int*)malloc(sizeof(int) * N);
    int *V = (int*)malloc(sizeof(int) * N);
    int *dp = (int*)calloc(maxweight + 1, sizeof(int));

    for (int i = 0; i < N; i++)
        scanf("%d %d", &W[i], &V[i]);

    for (int i = 0; i < N; i++) {
        for (int w = maxweight; w >= W[i]; w--) {
            dp[w] = max(dp[w], dp[w - W[i]] + V[i]);
        }
    }

    printf("%d\n", dp[maxweight]);

    free(W);
    free(V);
    free(dp);
    return 0;
}