happy coding

수업을 듣고 정리한 내용입니다. 배낭 문제는 0-1 배낭 문제라고 말하기도 하는데, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi가 주어지고, 배낭 용량이 C일 때, 최대 가지 값을 구하는 알고리즘이다. 단, 배낭에 담은 물건의 무게 합이 C를 초과하지 않으며, 각 물건은 1개씩 넣을 수 있다. 이 알고리즘의 부분문제는 i=1,2,...n이고, w = 1,2, ... c라고 가정한 상황에서 K[i,w] = 물건1 부터 i까지만 고려하고, (임시)배낭의 용량이 w일 때의 최대 가치 로 둔다. 여기서 물건은 행이고, 배낭의 용량은 열이다. Knapsack 입력 : 배낭의 용량은 c, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi, 단 i=1, 2, ... n 출력 : K[n,C] for i = 0..

수업을 듣고 정리한 내용입니다. Chained Matrix Multiplications 동적계획 알고리즘에서 연속행렬곱셈은 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제이다. 이 행렬에서 알고리즘은 결합 법칙을 허용하고, 주어진 행렬의 순서를 지켜서 반드시 이웃하는 행렬끼리 곱하도록 합니다. //연속 행렬 곱셈 입력 : 연속된 행렬 A1 * A2 ... * An, 단 A1은 d1 * d2, An = d(n-1) * d(n) 출력 : 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수 for i = to n C[i,j] = 0 for L = 1 to n - 1 for i = 1 to n - L j = i + L C[i,j] = 무한대 for k = 0 to j-1 temp = C[i,..