[12865] 평범한 배낭

문제 링크 : https://www.acmicpc.net/problem/12865

12865 - 평범한 배낭

본문

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 $N$개의 물건이 있다. 각 물건은 무게 $W$와 가치 $V$를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 $V$만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 $K$만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 $N$($1 \leq N \leq 100$)과 준서가 버틸 수 있는 무게 $K$($1 \leq K \leq 100000$)가 주어진다. 두 번째 줄부터 $N$개의 줄에 거쳐 각 물건의 무게 $W$($1 \leq W \leq 100000$)와 해당 물건의 가치 $V$($0 \leq V \leq 1000$)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

• $1 \leq N \leq 100$
• $1 \leq K, W \leq 100000$
• $0 \leq V \leq 1000$

---

풀이

냅색 알고리즘을 연습해볼 수 있는 문제이다. 추가적인 내용 없이 아예 기본적인 문제라서 설명은 생략한다. 냅색 알고리즘 자체에 관한 내용은 아래를 참고하자.

참고로, 이 풀이는 냅색 알고리즘의 “백트래킹” 풀이로, 최적화를 전혀 진행하지 않은 코드이다. 문제 조건이 빡빡하다면 제한에 걸리는 해답이지만, 문제 조건이 널널해서 직관적인 방법으로 푼 것임에 유의하자.

• 참고 알고리즘 : 냅색 알고리즘

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 30

#include <stdio.h>

typedef struct Good {
    int w;
    int v;
} GD;

#define MAX_IDX 100
#define MAX_WEIGHT 100000

#define INIT -1
int dp[MAX_IDX + 1][MAX_WEIGHT + 1];
GD arr[MAX_IDX];
int n, k;

#define max(a, b) (((a) > (b)) ? (a) : (b))

int knapsack(int cnt, int cap) {
    if (cnt == n) {
        return 0;
    } else if (dp[cnt][cap] != INIT) {
        return dp[cnt][cap];
    }

    int temp = knapsack(cnt + 1, cap);    // not choose
    if (arr[cnt].w <= cap) {
        temp = max(temp, knapsack(cnt + 1, cap - arr[cnt].w) + arr[cnt].v);
    }
    return dp[cnt][cap] = temp;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        arr[i] = (GD){a, b};
    }

    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= MAX_WEIGHT; ++j) {
            dp[i][j] = INIT;
        }
    }

    printf("%d", knapsack(0, k));
    return 0;
}

• dp[i][j] : $i$번째 물건까지 고려하였을 때, 배낭의 용량이 $j$일 때 얻을 수 있는 가치의 최댓값을 기록