Dynamic Programming - GitDeveloperKim/DreamEach GitHub Wiki
-
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
-
이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다
-
다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식으로 구성 (bottom-up, top-down)
-
다음의 조건을 만족할 때 사용 가능
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결
- 중복 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제가 반복적으로 해결
- 한번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은문제를 다시 호출하면 메모했던 결과를 가져옴
- 값을 기록해 놓는다는 점에서 캐싱(caching)
- 점화식이란 인접한 항들 사이의 관계식
- knapsack은 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제를 의미한다
- 최적의 원리(Principle of Optimality) : 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분 사례에 대한 최적해를 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.
- dp[i][w] : 배낭의 남은 무게(한도)가 w일때 i번째 보석(물건)까지 사용하여 조합 가능한 최대 가치합
- 보석이 유한할 때 (0-1)
-> if (j-w[i] < 0) : dp[i-1,w] // 채울 용량이 없을 때 i번째 보석 안 넣고 이전 값 가져오기
-> else(j-w[i] >=0) : max(value[i] + dp[i-1][j-w[i]] , dp[i-1][j]) // i 번째 보석을 안 넣고 그대로 가져오는 것과 i번째 보석을 넣을 때 비교 - 보석이 무한할 때
-> 이전에 채웠던 것에 내 무게를 더한 것과 이전에 구한 값과 비교하여 가치가 더 큰것을 택한다
-> dp[i][j] = max(dp[i][j-1], dp[i][j-w[i]]+value[i]) // i번째 보석을 안쓰는 경우와 이전 값에 i번째 보석을 추가하는 것 비교
click
click
import java.util.Scanner;
public class Main {
public static int N,K;
public static int []w = new int[100000];
public static int []v = new int[100000];
public static int [][] d = new int [101][100001];
// d[i,w] : i개의 보석이 있고 배낭의 무게한도가 w일때 최적의 이익
public static void main(String[] args) {
Scanner in = new Scanner (System.in);
N = in.nextInt(); // 보석의 개수
K = in.nextInt(); // 최대 용량
for (int i = 1; i <= N; i++) {
w[i] = in.nextInt(); // 보석의 무게
v[i] = in.nextInt(); // 보석의 가치
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
if (j-w[i] >= 0) {
d[i][j] = Math.max(d[i-1][j],d[i-1][j-w[i]] + v[i]);
} else {
d[i][j] = d[i-1][j];
}
}
}
System.out.println(d[N][K]);
}
}
| dp[i][j] (무게/값) | dp[][1] | dp[][2] | dp[][3] | dp[][4] | dp[][5] | dp[][6] | dp[][7] |
|---|---|---|---|---|---|---|---|
| 1번보석 (6/13) | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2번보석 (4/8) | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3번보석 (3/6) | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| 4번보석 (5/12) | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
n = Integer.parseInt(br.readLine());
input = new int[n+1];
dp = new int [n+1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= n; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
dp[1] = input[1];
int index = 1;
for (int i = 2; i <= n; i++) {
if (dp[index] < input[i]) {
dp[++index] = input[i];
} else {
/*
int j = 1;
for (j = 1; j <= index;j++) {
if (dp[j] >= input[i])
break;
}*/
dp[lower_bound(1,index,input[i])] = input[i];
}
}
sb.append(index+"\n");
- lower bound
private static int lower_bound (int s, int e, int v) {
while (s < e) {
int mid = (s+e)/2;
// v 찾고자 하는 값, dp[mid] 배열에서 중앙값
if (v <= dp[mid]) {
e = mid;
} else {
s = mid+1;
}
}
return e;
}
- upper bound
private static int upperBound(List data, int target) {
int begin = 0;
int end = data.size();
while(begin < end) {
int mid = (begin + end) / 2;
if(data.get(mid) <= target) {
begin = mid + 1;
}
else {
end = mid;
}
}
return end;
}