algorithm
동적 프로그래밍
수색…
소개
다이내믹 프로그래밍은 널리 사용되는 개념이며 자주 최적화에 사용됩니다. 복잡한 문제를 단순한 하위 문제로 재귀 적으로 분류하여 단순화하는 것을 말합니다. 일반적으로 Bottom up 방식입니다. 동적 프로그래밍을 "최적 하부 구조"및 "중복 하위 문제"로 적용하려면 두 가지 주요 특성이 있어야합니다. 최적화를 달성하려면 다이내믹 프로그래밍에서 암기 (Memorization)라는 개념을 사용합니다
비고
동적 프로그래밍은 Brute Force에 대한 개선입니다. 이 예제 를 통해 Brute Force에서 동적 프로그래밍 솔루션을 얻는 방법을 이해할 수 있습니다.
동적 프로그래밍 솔루션에는 2 가지 주요 요구 사항이 있습니다.
겹치는 문제
최적의 하부 구조
중복 문제는 원래 문제에 대한 해결책을 찾기 위해 문제의 작은 버전의 결과가 여러 번 재사용된다는 것을 의미합니다.
Optimal Substructure 는 하위 문제로부터 문제를 계산하는 방법이 있음을 의미합니다.
동적 프로그래밍 솔루션에는 주 및 전환 이라는 두 가지 주요 구성 요소가 있습니다.
국가 는 원래 문제의 하위 문제를 나타냅니다.
전환 은 하위 문제를 기반으로 문제를 해결하는 방법입니다.
동적 프로그래밍 솔루션에 소요되는 시간은 [상태 수 No. of States * Transition Time 으로 계산할 수 있습니다. 따라서 해가 N^2 상태이고 전이가 O(N) 일 경우, 해는 대략 O(N^3) 시간이 걸릴 것입니다.
배낭 문제
0-1 배낭
배낭 문제는 각 가중치, 값 및 정확히 1 개의 사본을 가진 일련의 항목이 주어지면 전체 가중치가 주어진 것보다 작거나 같도록 어떤 항목을 모음에 포함할지 결정합니다 최대 값은 가능한 한 클 수 있습니다.
C ++ 예제 :
구현 :
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
테스트 :
3 5
5 2
2 1
3 2
출력 :
3
즉, 최대 값을 얻을 수 있다는 의미는 3이며, (2,1)과 (3,2)를 선택하면됩니다.
무제한 배낭
Unbounded 배낭 문제는 가중치, 값 및 무한 사본이 있는 일련의 항목이 있으면 컬렉션에 포함 할 각 항목의 수를 결정하여 총 가중치가 주어진 한도보다 작거나 같도록하는 문제입니다 총 가치는 가능한 한 커집니다.
파이썬 (2.7.11) 예 :
구현 :
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
그 구현의 복잡성은 O(nC) 이며, n은 항목의 수입니다.
테스트 :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
출력 :
20
즉, 최대 값을 얻을 수 있다는 의미는 20, 이는 (5, 8), (5, 8) 및 (3, 4)를 선택하여 얻을 수 있습니다.
가중치 작업 스케줄링 알고리즘
가중치 작업 스케줄링 알고리즘은 또한 가중치 작업 선택 알고리즘으로 표시 될 수 있습니다.
문제는 시작 시간과 종료 시간이있는 특정 작업과 작업 완료시 얻는 수익을 고려해 볼 때 병렬로 두 가지 작업을 실행할 수 없다면 주어진 최대 이익은 얼마입니까?
이것은 Greedy Algorithm을 사용하여 활동 선택과 비슷하게 보이지만 추가 된 것이 있습니다. 즉, 완료된 작업 수를 최대화하는 대신 최대 이익을 얻는 데 집중합니다. 수행 된 작업의 수는 여기에서 중요하지 않습니다.
예제를 살펴 보겠습니다.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
작업은 이름, 시작 및 종료 시간 및 이익으로 표시됩니다. 몇 차례 반복 한 후에 우리는 Job-A 와 Job-E 를 수행 할 수 있는지를 알 수 있습니다. 최대 이익은 17입니다. 알고리즘을 사용하여이를 어떻게 찾을 수 있습니까?
우리가해야 할 첫 번째 일은 끝내는 순서로 작업을 마무리하는 것입니다. 왜 우리가이 일을합니까? 우리가 끝내는 시간이 덜 걸리는 일을 선택하면 다른 일을 선택하는 데 가장 많은 시간을 둡니다. 우리는 :
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
추가 임시 배열 Acc_Prof 의 크기가 n입니다. 여기서 n 은 총 작업 수를 나타냅니다. 여기에는 작업 수행의 누적 된 최대 이익이 포함됩니다. 이해 못 하겠어? 기다려 봐. 각 작업의 이익으로 배열의 값을 초기화합니다. 즉, Acc_Prof [i] 는 i 번째 작업 수행의 이익을 우선적으로 유지합니다.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
이제 위치 2 를 i 로 표시하고 위치 1 은 j 로 표시합니다. 내가 N + 1이 될 때까지 우리의 전략이 반복 될 때마다 I-1 이후 1에서 J를 반복하는 것입니다, 우리는 1 전을 증가합니다.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
작업 [I]과 작업 [J] 중복, 즉, 작업 [J]의 종료 시간은 작업보다 큰 경우 [I]의 시작 시간은 다음 두 가지 작업을 함께 수행 할 수없는 경우 우리는 확인한다. 그러나 겹치지 않으면 Acc_Prof [j] + Profit [i]> Acc_Prof [i]인지 확인 합니다. 이 경우 Acc_Prof [i] = Acc_Prof [j] + Profit [i]를 업데이트 합니다. 그건:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
여기서 Acc_Prof [j] + Profit [i] 는이 두 작업을 수행 한 누적 된 이익을 나타냅니다. 우리의 예를 들어 보겠습니다.
여기서 Job [j] 는 Job [i] 와 중복됩니다. 그래서 이것들은 함께 할 수 없습니다. 우리 J는 I-1과 동일하기 때문에, 우리는 3 I + 1 i 값을 증가. 그리고 우리는 j = 1로 만듭니다.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
이제 작업 [j] 와 작업 [i] 은 겹치지 않습니다. 이 두 작업을 선택하여 얻을 수있는 총 이익은 다음과 같습니다 : Acc_Prof [j] + Profit [i] = 5 + 5 = 10 이는 Acc_Prof [i] 보다 큽니다 . 따라서 Acc_Prof [i] = 10을 업데이트합니다. 또한 j 를 1 씩 증가시킵니다.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
여기서 Job [j] 는 Job [i] 와 겹치며 j 도 i-1 과 같습니다. 그래서 i 를 1 씩 증가시키고 j = 1로 만듭니다. 우리는,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
이제 Job [j] 와 Job [i] 는 겹치지 않습니다. Acc_Prof [i] 보다 큰 5 + 4 = 9 의 누적 이익을 얻습니다. Acc_Prof [i] = 9를 업데이트하고 j 를 1 씩 증가시킵니다.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
다시 Job [j] 와 Job [i] 는 겹치지 않습니다. 축적 된 이익은 6 + 4 = 10 이며 이는 Acc_Prof [i] 보다 큽니다 . Acc_Prof [i] = 10을 다시 업데이트합니다. j 를 1 씩 증가시킵니다.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
이 프로세스를 계속하면 i를 사용하여 전체 테이블을 반복 한 후 테이블이 마침내 다음과 같이 보입니다.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* 문서를 짧게 만들려면 몇 단계를 건너 뛰었습니다.
Acc_Prof 배열을 반복 할 경우 최대 이익은 17이됩니다 ! 의사 코드 :
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
Acc_Prof 배열을 채우는 복잡성은 O (n 2 )입니다. 배열 탐색에는 O (n)이 필요 합니다. 따라서이 알고리즘의 전체 복잡도는 O (n 2 )입니다.
이제 우리는 작업이 최대의 이익을 얻기 위해 수행 된 찾을하려는 경우, 우리는 역순으로 배열을 통과해야하고 Acc_Prof가 maxProfit 일치하는 경우, 우리의 이익을 스택에 작업의 이름을 누르고 빼는 것 그 직업을 maxProfit에서 . maxProfit> 0 이 될 때까지 또는 Acc_Prof 배열의 시작점에 도달 할 때까지이 작업을 수행합니다. 의사 코드는 다음과 같습니다.
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
이 절차의 복잡성은 다음과 같습니다. O (n) .
한 가지 기억해야 할 것은 최대 이익을 제공 할 수있는 여러 개의 작업 일정이있는 경우이 절차를 통해서만 하나의 작업 일정을 찾을 수 있다는 것입니다.
거리 편집
문제 문은 str1과 str2의 두 문자열이 주어지고 str1에 대해 str2로 변환 될 수있는 연산의 최소 개수를 지정하는 것과 같습니다.
Java로 구현
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
산출
3
가장 긴 공통 서브 시퀀스
두 개의 문자열을 받았다면 두 문자열 모두에서 가장 긴 공통 서브 시퀀스를 찾아야합니다.
예
입력 용 LCS 시퀀스 "ABCDGH"및 "AEDFHR"은 길이가 3 인 "ADH"입니다.
입력 용 LCS 시퀀스 "AGGTAB"및 "GXTXAYB"는 길이가 4 인 "GTAB"입니다.
Java로 구현
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
산출
4
피보나치 수
동적 프로그래밍을 사용하여 n 번째 피보나치 수를 인쇄하기위한 상향식 접근법입니다.
재귀 트리
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
겹치는 하위 문제
여기 fib (0), fib (1) 및 fib (3)은 중첩되는 하위 문제입니다 .fib (0)은 3 번 반복되고 fib (1)은 5 번 반복되고 fib (3)은 2 번 반복됩니다 타임스.
이행
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
시간 복잡성
에)
가장 긴 공통 부분 문자열
2 문자열 str1과 str2가 주어 졌을 때 가장 긴 공통 부분 문자열의 길이를 찾아야합니다.
예제들
입력 : X = "abcdxyz", y = "xyzabcd"출력 : 4
가장 긴 공통 부분 문자열은 "abcd"이며 길이는 4입니다.
입력 : X = "zxabcdezy", y = "yzabcdezx"출력 : 6
가장 긴 공통 부분 문자열은 "abcdez"이며 길이는 6입니다.
Java로 구현
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
시간 복잡성
O (m * n)
