백준 12865번: 평범한 배낭

문제

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

12865번: 평범한 배낭

 

---

풀이

여행에 필요하다고 생각하는 n개의 무게와 가치를 가지는 물건이 있을 때 최대 k만큼의 무게만을 넣을 수 있는 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp 배열은 임의의 수 x, y가 있을 때 1번부터 x번 사이에서 물건을 여러 개 골랐을 때 가방이 더 버틸 수 있는 무게가 y인 배낭이 갖는 물건들의 가치의 최댓값을 의미합니다.

knapsack 함수에서 dp[x][y]가 null이라면 x번 물건의 무게 weight[x]가 y보다 큰지 확인합니다. 만약 크다면 가방에 해당 물건을 넣을 수 없다는 뜻이므로 knapsack(x - 1, y)을 통해 dp[x - 1][y]을 받아 dp[x][y] 값에 넣어주고 작거나 같다면 knapsack 함수를 통해 해당 물건을 넣지 않은 dp[x - 1][y]와 해당 물건을 넣은 dp[x - 1][y - weight[x]]에 해당 물건의 가치 value[x]을 더한 값 중에서 큰 값을 넣어준 뒤에 그 값을 반환합니다.

모든 입력이 끝나면 knapsack(n, k)을 실행하여 dp[n][k] 값을 받아 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static Integer[][] dp;
    static int[] weight, value;

    public static int knapsack(int x, int y) {
        if (x == 0) return 0;
        if (dp[x][y] == null) {
            if (weight[x] > y) {
                dp[x][y] = knapsack(x - 1, y);
            } else {
                dp[x][y] = Math.max(knapsack(x - 1, y), knapsack(x - 1, y - weight[x]) + value[x]);
            }
        }
        return dp[x][y];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        dp = new Integer[n + 1][k + 1];
        weight = new int[n + 1];
        value = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(knapsack(n, k));
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp 배열은 탑다운 방식의 코드에서의 의미와 동일합니다. i와 j를 포함한 이중 for문에서 j는 가방이 더 버틸 수 있는 무게이고 i번 물건의 무게 weight[i]가 j보다 큰지 확인합니다. 만약 크다면 가방에 해당 물건을 넣을 수 없다는 뜻이므로 dp[i][j]에 dp[i - 1][j]을 넣어주고 작거나 같다면 가방에 해당 물건을 넣을 수 있으므로 해당 물건을 넣지 않은 dp[i - 1][j]와 해당 물건을 넣은 dp[i - 1][j - weight[i]]에 해당 물건의 가치 value[i]을 더한 값 중에서 큰 값을 넣어줍니다.

모든 입력이 끝나면 dp[n][k] 값을 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
main() {
	int n, k;
	scanf("%d %d", &n, &k);
	int* weight = (int*)malloc(sizeof(int) * (n + 1));
	int* value = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &weight[i], &value[i]);
	}
	int** dp = (int**)malloc(sizeof(int*) * (n + 1));
	for (int i = 0; i <= n; i++) {
		dp[i] = (int*)malloc(sizeof(int) * (k + 1));
		for (int j = 0; j <= k; j++) {
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (weight[i] > j) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = math_max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
			}
		}
	}
	printf("%d", dp[n][k]);
}

 

---

결론

대표적인 dp 문제 중 하나인 "냅색 문제"를 풀어봤습니다. LCS 문제와 마찬가지로 탑다운 방식을 이용한 코드에서 dp 배열을 Integer가 아니라 int로 잡으면 0인 경우가 너무 많을 것 같았습니다.