제출 코드
- 사용 알고리즘 :
DP (Knapsack)
DP의 대표적인 문제인, 배낭채우기 문제의 표본 그 자체였다.
해당 물건(row)을 고려하여 (col)무게를 최대로 하는 배낭을 채울 때, 배낭의 최댓값을 배열에 저장한다. 물건들을 하나씩 순차적으로 넣어가면서 (행 for구문), 배낭의 총 무게를 늘려간다(열 for구문).
점화식을 세우면 다음과 같다.
n번째 물건의 무게 = w, 가치 = v
dp[n][k] = dp[n-1][k]$ $(if$ $k< weight)
= max(dp[n-1][k], dp[n-1][k-weight]+value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class G12865_nomalKnapsack {
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());
int[][] naps = new int[N+1][K+1];
Arrays.fill(naps[0], 0);
for(int n=1; n<=N; n++) {
naps[n][0] = 0;
st = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(st.nextToken());
int value = Integer.parseInt(st.nextToken());
for(int k=1; k<=K; k++) {
if(k < weight) naps[n][k] = naps[n-1][k];
else naps[n][k] = Math.max(naps[n-1][k], naps[n-1][k-weight]+value);
}
}
System.out.println(naps[N][K]);
}
}