[Jungle] Week3. Knapsack problem | LCS(Longest Common Subsequence)

배낭 문제(knapsack problem)

• 분할 가능한 배낭 문제 - 짐을 쪼갤 수 있을 때. 짐의 무게가 소수일 수 있는 경우
• 0-1 배낭 문제 - 짐을 쪼갤 수 없을 때. 짐의 무게는 0 이상의 정수만 가능한 경우

현재 배낭 무게 한도보다 들어가고자 하는 물건 무게가 크면 이전의 값을 그대로 가져간다.
그렇지 않고 물건이 들어갈 수 있는 경우에는 넣는 경우/넣지 않는 경우 중에 큰 값을 결정한다.

N, K = map(int, input().split())
lst = [[0,0]]

for _ in range(N):
	lst.append(list(map(int, input().split()))) 
   
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(1, N+1);
	for j in range(1, K+1):
    	weight = lst[i][0]
        value = lst[i][1]
        if j < weight: 
        	dp[i][j] = dp[i-1][j]
          
        else:
        	dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)
           
print(dp[N][K])

금송아지 옮기기와 금가루 옮기기

Fractional Knapsack Problem (분할 가능한 배낭 문제)

-> 분할이 가능하기 때문에
정렬하여 순차적으로 가방에 담는 것이 최선의 선택이 될 수 있을 것.
각 단계에서 가치가 높은 물건 선택해서 가방 채워넣는 것이 최적의 선택이 될 것!

0-1 Knapsack Problem

-> 분할할 수 없는 경우
그리디로 구하면 최적의 해를 구하지 못할 수도 있다.
-> 이전 선택이 이후 선택에 영향을 미치기 때문에 동적 계획법이 적합하다.

Longest Common Subsequence, 최장 공통 부분 수열 vs. Longest Common Substring, 최장 공통 문자열

LCS(Longest Common Subsequence): 최장 공통 부분 수열

두 수열이 주어졌을 때 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기

if i ==0 or j ==0:
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i-1][j-1] + 1 
else:
	LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

LCS(Longest Common Substring) 최장 공통 부분 문자열

if i ==0 or j ==0 :
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i-1][j-1] + 1 
else:
	LCS[i][j] = 0

----

참고) 
https://straw961030.tistory.com/209