백준 : 12865번, 평범한 배낭

문제 주소 : www.acmicpc.net/problem/12865

정답 비율 : 36.156% (2021.02.20 21:20 기준)

12865번: 평범한 배낭

 

문제 요약 : 

N개의 물건의 무게(W)와 가치(V)가 주어집니다. 가방에 최대 무게 K만큼 담을 수 있을 때 가방에 담은 물건 들의 가치 합의 최댓값을 알아내시오.

 

문제 조건 :

입력 : N( 1 ~ 100 ), K( 1 ~ 100000 ), W( 1 ~ 100000 ), V( 0 ~ 1000 )

출력 : 가방에 넣은 물건들의 가치 합의 최댓값 출력

시간 : 2 초

 

문제 풀이 :

전형적으로 DP를 사용하는 Knapsack 문제입니다. (사실 해당 문제를 공부하기 전에는 잘 몰랐습니다.)

 

해당 문제를 가장 먼저 떠오른 것은 모든 경우의 수를 조사하는 것이었습니다.

 

코드는 다음과 같습니다. (시간 초과로 실패)

bag = [[0, 0]]
n, k = list(map(int, input().split()))

for i in range(n):
    tmp = list(map(int, input().split()))
    bag += [[tmp[0] + a, tmp[1] + b] for a, b in bag if a + tmp[0] <= k]

print(max(b[1] for b in bag))

 

DP를 사용한 코드는 다음과 같습니다.

 

C99 - 2차원 배열 풀이

 

#include<stdio.h>

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

int V[100];
int W[100];
int DP[101][100001];

int main()
{
	int N, K, i = -1, j = -1;
	scanf("%d %d",&N, &K);
	
	for(i = 0; i < N ;i++)
		scanf("%d %d", &W[i], &V[i]);
		
	for(i = 0; i < N; i++)
	{
		for(j = 1; j <= K; j++)
		{
			if(W[i] <= j)
				DP[i + 1][j] = MAX(DP[i][j], DP[i][j - W[i]] + V[i]);
			else
				DP[i + 1][j] = DP[i][j];
		}
	}
	
	printf("%d", DP[N][K]);
	
	return 0;
}

 

Python3 - 1차원 배열 풀이

#solve 12865
n, k = list(map(int, input().split()))
bag = [0 for i in range(k + 1)]

for i in range(n):
    w, v = list(map(int, input().split()))
    for j in range(k, 1, -1):
        if w <= j:
            bag[j] = max(bag[j], bag[j - w] + v)

print(bag[k])