3282. 0/1 Knapsack
- 0/1 Knapsack알고리즘은 다이나믹 프로그래밍으로 해결할 수 있다.
가방에 담을 수 있는 물건의 부피와 가치는 다음과 같다.
DP 테이블을 만들어 보자
1.
물건 1일 때이다. 생각할 수 있는 경우의 수는 물건1을 골랐을 때, 물건1을 고르지 않았을 때이다. 물건1을 골랐을 때 가치는 2 + 0(0행에서의 나머지 부피값)이다. 예를 들어보자면 부피가 3일 때를 생각해보자
물건1을 고르면 가치는 2가 되고 나머지부피 3-2=1을 (0행, 부피 1일 때)값 0을 가져오는 것이다.
반면에 물건1을 고르지 않았을 때에는 바로 위에 값을 비교하면 되는 것이다.
물건2일 때이다. 마찬가지로 물건2를 골랐을 때, 고르지 않았을 때를 비교해서 최대값을 dp테이블에 저장하면 된다. 물건2는 부피가 3이다. 그래서 1,2는 물건2를 골랐을 때 경우의 수를 제외한 고르지 않았을 때 값(바로 위값)을 가져오면 되는 것이다. 부피 5일 때를 생각해보자
부피 5는 물건2의 부피인 3이상이므로 고를 수 있다. 그러면 가치는 2 + 2(1물건의 2부피값)을 가져오면 된다.
마찬가지로 물건3일 때를 생각해보자
부피가 5일 때에는 물건3을 고를 수 있고, 만약 고른다면 4 + 2(나머지 부피는 1이고 물건3을 제외한 최대값을 구해야 하므로 물건2의 부피1값을 가져오면 됨) 6이 된다.
물건 4일 때를 생각해보자
부피가 5일 때에는 물건 4를 고를 수 있고, 만약 고른다면 3 + 2(나머지 부피 3이고 물건 4를 제외한 최대값은 물건3의 부피3값을 가져오면 됨) 5가 된다.
반면에 고르지 않는다면 6이다. 그래서 최대값은 6이 된다.
이것을 코드로 나타내면 다음과 같다.
T = int(input())
ans = []
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n, k = map(int, input().split(" "))
case = []
for _ in range(n):
tmp = list(map(int, input().split(" ")))
case.append(tmp)
dp = [[0 for i in range(k+1)] for j in range(n+1)]
for i in range(1, n + 1):
for j in range(1, k + 1):
if case[i-1][0] <= j:
dp[i][j] = max(case[i-1][1] + dp[i-1][j - case[i-1][0]], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
print("#" + str(test_case) + " " + str(dp[n][k]))