Coding StudyRoom

Serial Monadic DP : next solution의 최적 해를 구하기 위해 바로 이전 level의 subproblem의 최적 해의 값이 사용되고, 이러한 DP 식에서 재귀식이 한 개인 경우. 예제 1) The Shortest-Path Problem (최단 경로 문제) : 시작 노드(S)에서 끝 노드(R) 까지의 최단 경로를 구하는 문제이다. 문제설명 : - weighted multistage graph(다단계 그래프) 이고 r + 1 개의 levels로 구성되었다. 예시 그림) - level i의 모든 노드들은 level i + 1 의 모든 노드들과 연결되어 있다. (그림과는 다름) - level 0 은 시작 노드(S), level r 은 끝 노드(R)로 노드가 1개 뿐이다. functiona..

문제 : 배낭에 담을 수 있는 무게의 최댓값(15kg)이 정해져 있다. 각각 짐의 가치와 무게가 (4$, 12kg), (2$, 1kg), (10$, 4kg), (1$, 1kg), (2$, 2kg)인 경우 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록했을 때의 최대 $는? 짐을 쪼갤 수 있는 경우 > 그리디 알고리즘으로 해결 짐을 쪼갤 수 없는 경우 > 다이나믹 프로그래밍으로 해결 #그리디 알고리즘 배낭 문제 def fractional_knapsack(cargo): capacity = 15 #배낭 수용량 pack = [] total_price = 0 #단가 계산 역순 정렬 for c in cargo: pack.append((c[0] / c[1], c[0], c[1])) pack.sort(key=lamb..