알고리즘 썸네일형 리스트형 0-1 Knapsack Problem(배낭 채우기) 문제어떤 도둑이 배낭을 메고 집에 침입, 도둑은 각 물건의 '무게'와 '값어치'를 알고 있다. 훔칠 물건의 총 무게는 배낭의 용량을 초과할 수 없다.배낭에 담을 수 있는 최대 값어치를 구해보자 입력•보석 (item)의 개수: n•보석 집합 S = {item1, item2,…, itemn}•wi = itemi의 무게, pi = itemi의 가치 •W = 배낭에 넣을 수 있는 총 무게 목표 maximize subject to and .여기서 x는 i번째 아이템을 배낭에 넣을 것인지 넣지 않을 것인지에 대한 1, 0 값 출처 링크 : wikipedia.org Brute-force 방법- 모든 가능한 경우를 반복하면서 w를 초과하기 않으면서 총 이 익을 최대로 하는 경우를 찾는다.- 각 물건의 포함/불포함 여부.. 더보기 가중치 방향 그래프(weighted directed graph)의 최단 경로 찾기 문제가중치 방향 그래프(weighted directed graph)의 한 정점(vertex)에서 다른 정점으로 갈 수 있는 경로 중 가중치가 가장 작은 경로의 가중치를 구해보자 알고리즘[편집]아래는 이 문제를 해결하기 위한 주요 알고리즘들이다.데이크스트라 알고리즘 : 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.벨먼-포드 알고리즘 : 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.A* 탐색 알고리즘 : 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.플로이드-와셜 알고리즘 : 전체-쌍 최단 경로 문제를 풀 수 있다. 출처 : wikipedia.org 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든.. 더보기 이전 1 다음
