배낭 문제와 동적 계획법
대부분의 배낭 문제들은 01 배낭으로 변환한 후 복잡도를 최적화하는 방식으로 접근한다.
01 배낭 문제
각 물건은 선택하거나 선택하지 않는 두 가지 경우만 존재한다. 0과 1의 관계에 해당하기 때문에 01 배낭이라고 명칭한다.
dp[i][j]를 앞에서부터 i개의 물건 중容量 j의 배낭이 담을 수 있는 최대 가치라고 정의하자.
i번째 선택지는 i-1번째에서 전이되어 온다. i번째 물건에 대해 선택하거나 선택하지 않을 수 있는데, 선택하지 않으면 dp[i-1][j]가 되고, 선택하면 dp[i-1][j-v[i]] + w[i]]에서 전이된다.
이 경우 시간 복잡도와 공간 복잡도는 O(nk)가 된다.
하지만 자세히 관찰해보면, i번째 선택은 i-1번째 선택과만 관련이 있다. 따라서 첫 번째 차원을滚动 처리할 수 있다.
dp[j]와 dp[j-v[i]] + w[i]]로 업데이트할 때, dp[j-v[i]]가 i-1 시점의 값이 되어야 하므로, j를 역순으로枚举하여 dp[j-v[i]]가 아직 업데이트되지 않았음을 보장해야 한다.
for (int i = 1; i <= n; i++) {
for (int j = V; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
다차원 비용 배낭 문제
별도의 루프를 중첩하면 된다. 2차원을 예로 들면 다음과 같다:
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-weight[i]][k-memory[i]] + value[i])for (int i = 1; i <= n; i++) {
for (int j = V; j >= weight[i]; j--) {
for (int k = M; k >= memory[i]; k--) {
dp[j][k] = max(dp[j][k], dp[j - weight[i]][k - memory[i]] + value[i]);
}
}
}
완전 배낭 문제
枚举 순서를 변경하면, dp[i][j]가 weight[i] ≤ j 조건에서 dp[i-1][j-weight[i]]로 여러 번 업데이트된다. 이는 물건 i를 여러 번 배낭에 넣는 것과 동일한 효과를 가져온다.
for (int i = 1; i <= n; i++) {
for (int j = weight[i]; j <= V; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
다중 배낭 문제
각 물건이 k_i개만큼 존재하는 경우이다.
이를 k_i개의 서로 다른 물건으로 보고, 각각 한 번씩 선택할 수 있다면 01 배낭 문제로 변환된다.
복잡도는 O(W × Σk_i)가 된다.
이 복잡도는 여전히 최적화할 여지가 있다.分组 과정을 최적화해보자.任意의 수는 2의 거듭제곱으로 분해할 수 있다.
따라서 이진 분할을 통해 최적화한다.
int n = read(), V = read();
for (int i = 1; i <= n; i++) {
int w = read(), v = read(), cnt = read();
int cur = 1;
while (cnt - cur >= 0) {
cnt -= cur;
items[++idx].weight = cur * w;
items[idx].value = cur * v;
cur *= 2;
}
if (cnt > 0) {
items[++idx].weight = w * cnt;
items[idx].value = v * cnt;
}
}
이렇게 분할한 후 01 배낭을 적용하면 된다.
복잡도는 O(W × Σlog₂k_i)가 된다.
선형 동적 계획법
최장 공통 부분 수열과 최장 증가 부분 수열
이번에는 O(n log n)求解 방법만 설명한다.
dp[i]를 길이 i인 최장 증가 부분 수열의 마지막 요소 크기라고 정의한다.
당연히 dp[1] = arr[1]이다.
만약 arr[i] > dp[len]이라면 길이 뒤에 바로 연결할 수 있으므로 dp[++len] = arr[i]이다.
그렇지 않다면 첫 번째로 자신보다 큰 수를 찾아 교체한다. 이렇게 하면 더 나은 결과를 얻을 수 있다.
int n, arr[MAXN], brr[MAXN];
int pos[MAXN], dp[MAXN], len;
int main() {
n = read();
for (int i = 1; i <= n; i++) {
arr[i] = read();
pos[arr[i]] = i;
}
for (int i = 1; i <= n; i++) {
brr[i] = read();
brr[i] = pos[brr[i]];
}
dp[1] = brr[1];
len = 1;
for (int i = 2; i <= n; i++) {
if (brr[i] >= dp[len]) {
dp[++len] = brr[i];
} else {
int idx = upper_bound(dp + 1, dp + len + 1, brr[i]) - dp;
dp[idx] = brr[i];
}
}
print(len);
return 0;
}
최장 공통 증가 부분 수열 (LCIS)
LCS도 간단하고 LIS도 간단하다. 그럼 LCIS도 마찬가지로 간단하다.
int n, m, arr[N], brr[N];
int dp[1000][1000], prev[1000][1000];
int result[N], cnt = 0;
int main() {
n = read();
for (int i = 1; i <= n; i++) arr[i] = read();
m = read();
for (int i = 1; i <= m; i++) brr[i] = read();
arr[0] = brr[0] = -INF;
for (int i = 1; i <= n; i++) {
int best = 0, idx = 0;
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i-1][j];
prev[i][j] = j;
if (arr[i] == brr[j]) {
if (dp[i][j] < best + 1) {
dp[i][j] = best + 1;
prev[i][j] = idx;
}
}
if (arr[i] > brr[j]) {
if (dp[i-1][j] > best) {
best = dp[i-1][j];
idx = j;
}
}
}
}
int ans = 0, position = 0;
for (int i = 1; i <= m; i++) {
if (dp[n][i] > ans) {
ans = dp[n][i];
position = i;
}
}
printf("%d\n", ans);
int i = n, j = position;
while (i >= 1 && j >= 1) {
if (prev[i][j] != j) {
result[++cnt] = brr[j];
}
j = prev[i][j];
i--;
}
for (int i = cnt; i >= 1; i--) {
printf("%d ", result[i]);
}
return 0;
}