연속 행렬 곱셈
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
33
34
35
36
37
38
39
40
41
42
43
44
45
public class MatrixMultiplication {
public static void main(String[] args) {
Matrix[] array = new Matrix[4];
array[0] = new Matrix(10, 20);
array[1] = new Matrix(20, 5);
array[2] = new Matrix(5, 15);
array[3] = new Matrix(15, 30);
int n = array.length;
int[][] C = new int[n][n];
// Step 1
for (int i = 0; i < n; i++) {
C[i][i] = 0;
}
// Step 2-6
for (int L = 2; L <= n; L++) {
for (int i = 0; i <= n - L; i++) {
int j = i + L - 1;
C[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int temp = C[i][k] + C[k + 1][j] + array[i].row * array[k].col * array[j].col;
if (temp < C[i][j]) {
C[i][j] = temp;
}
}
}
}
// Step 7
System.out.println("Minimum number of multiplications is: " + C[0][n - 1]);
}
}
class Matrix {
int row;
int col;
public Matrix(int row, int col) {
this.row = row;
this.col = col;
}
}
##연속 행렬 곱셈 (Chained Matrix Multiplications) 문제는 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제
o 10x20 행렬 A와 20x5 행렬 B를 곱하는데 원소 간의 곱셈 횟수는 10x20x5 = 1,000.
o 두 행렬을 곱한 결과 행렬 C는 10x5
o 3개의 행렬을 곱해야 하는 경우
o 연속된 행렬의 곱셈에는 결합 법칙 허용
o AxBxC = (AxB)xC = Ax(BxC)
##AxB를 계산한 후에 C를 곱하기
o AxB를 계산하는데 10x20x5 = 1,000번
o 결과 행렬의 크기가 10x5이고, 이에 행렬 C를 곱하면 10x5x15 = 750번
o 1,000 + 750 = 1,750회의 원소의 곱셈이 필요
##BxC를 계산한 후에 A를 곱하기
o BxC를 계산하는데 20x5x15 = 1,500번
o 그 결과 20x15 행렬이 만들어지고, 이를 행렬 A와 곱하면 10x20x15 = 3,000번
o 1,500 + 3,000 = 4,500회의 곱셈이 필요
배낭 문제 알고리즘
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
public class KnapsackProblem {
public static int knapsack(int C, int[] w, int[] v, int n) {
int[][] K = new int[n + 1][C + 1];
for (int i = 0; i <= n; i++) {
for (int w_temp = 0; w_temp <= C; w_temp++) {
if (i == 0 || w_temp == 0) {
K[i][w_temp] = 0;
} else if (w[i - 1] <= w_temp) {
K[i][w_temp] = Math.max(v[i - 1] + K[i - 1][w_temp - w[i - 1]], K[i - 1][w_temp]);
} else {
K[i][w_temp] = K[i - 1][w_temp];
}
}
}
return K[n][C];
}
public static void main(String[] args) {
int C = 50; // 배낭의 용량
int n = 3; // 물건의 개수
int[] w = {10, 20, 30}; // 각 물건의 무게
int[] v = {60, 100, 120}; // 각 물건의 가치
System.out.println(knapsack(C, w, v, n)); // 최대 가치 출력
}
}
해당 자바 코드는 0/1 배낭 문제를 해결하기 위한 동적 계획법 알고리즘입니다.
주어진 배낭의 용량 C과 n개의 물건 중에서 각 물건 i의 무게 wi와 가치 vi가 주어졌을 때, 최대한 가치를 최대화하는 경우를 찾아내는 문제입니다.
위 코드는 먼저 2차원 배열 K를 선언합니다. 이 배열은 K[i][w]가 i개의 물건을 고려하고 배낭의 용량이 w일 때 얻을 수 있는 최대 가치를 저장합니다.
그리고 첫 번째 for문에서는 K[0][w]를 0으로 초기화해줍니다. 이때, 물건 0이란 어떤 물건도 고려하지 않을 때를 의미합니다.
두 번째 for문에서는 K[i][0]을 0으로 초기화해줍니다. 이때, 배낭의 용량이 0일 때를 의미합니다.
세 번째 for문에서는 1부터 n까지 물건 i를 고려하면서 최대 가치를 구해나갑니다.
네 번째 for문에서는 임시로 배낭의 용량을 w로 두고, 현재 고려 중인 물건 i를 배낭에 담을지 말지를 결정합니다.
만약 물건 i의 무게가 임시 배낭의 용량을 초과한다면, 물건 i는 배낭에 담을 수 없습니다. 따라서 이 경우에는 이전에 고려했던 K[i-1][w] 값을 K[i][w]에 그대로 복사합니다.
하지만 물건 i의 무게가 임시 배낭의 용량을 초과하지 않는다면, 물건 i를 배낭에 담을 수 있습니다. 이때, 물건 i를 배낭에 담지 않았을 때의 최대 가치와 물건 i를 배낭에 담았을 때의 최대 가치 중 큰 값을 선택합니다.
이렇게 구한 최대 가치를 반환하면 됩니다.
따라서 위 코드는 동적 계획법을 활용해 0/1 배낭 문제를 해결하는 방법을 자바 코드로 구현한 것입니다.
