BOJ 12865 [평범한 배낭]

문제

문제보기

N개의 물건의 무게와 가치가 주어진다. 배낭에 실을 수 있는 무게의 한계 K가 주어질 때 가장 가치가 높은 배낭의 가치를 구하시오.

냅색 알고리즘

풀이

직전에 풀은 동전 문제와 유사한 문제이다. 하지만 동전은 반복해서 여러개를 사용할 수 있지만 물건은 하나만 실을 수 있다. 또한 동전에서 db table의 의미는 dp[i]는 i원을 만드는 경우의 수 이지만 배낭 문제에서 dp[n][i]는 n번째 물건까지 탐색했을 때 무게 i의 가방이 지닐 수 있는 최대가치이다.

동전때 처럼 1차원 배열을 쓰면 물건을 한번만 실는 건지 여러번 실는 건지 체크가 불가능하다. 이차원배열로 하고 dp[i-1]을 참고해서 dp[i]를 만들어야 dp[i-1]에는 i번째 item이 한번도 안쓰였으므로 i번째 item을 한번만 쓸 수 있다.

추가로 item별로 dp table을 따로 만들었으므로 이전의 결과를 밑에 반영하는 것이 중요하다.

n,k = map(int,input().split())
items = []

for _ in range(n):
	items.append(list(map(int,input().split())))
	
dp = [[0] * (k+1) for _ in range(n)]

for j in range(len(items)):
	for i in range(k+1):
		if i == items[j][0]:
			dp[j][i] = max(items[j][1],dp[j-1][i])
		else:
			if i-items[j][0]>=0 and dp[j-1][i-items[j][0]] != 0:
				dp[j][i] = max(dp[j-1][i],dp[j-1][i-items[j][0]]+items[j][1],dp[j][i-1])
			else:
				dp[j][i] = max(dp[j-1][i],dp[j][i-1])
		
print(dp[n-1][k])