Computer Science/Problem (4) 썸네일형 리스트형 [Problem] 배낭 문제의 그리디 알고리즘적 접근 (Knapsack, Greedy) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. 그리디 배낭 (GreedyKnapsack) 클래스 구현 class GreedyKnapsack(Knapsack): def get_algorithm(self): return 'Greedy' def fractional_solve(self): # TODO: 분할 배낭 문제를 그리디로 구현 3.3.1. 0-1 배낭 문제 접근 0-1 배낭 문제를 그리디 알고리즘적으로 접근할 수 있을까? DP에서 사용한 단위 무게당 가치의 개념을 다시 사용해보자. 물체를 단위 무게당 가치 내림차순으로 정렬한 다음 배낭에 넣을 수 있는 만큼 차례로 넣는다면 반드시 최고 가치를 가질 수 있을까? 그렇지 않다. 안타깝게도 단위.. [Problem] 배낭 문제의 동적 계획법 알고리즘적 접근 (Knapsack, Dynamic Programming) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. DP 배낭 (DPKnapsack) 클래스 구현 from functools import cmp_to_key from knapsack import Knapsack class DPKnapsack(Knapsack): def get_algorithm(self): return 'Dynamic Programming' def zero_one_solve(self): # TODO: 0-1 배낭 문제를 DP로 구현 def fractional_solve(self): # TODO: 분할 배낭 문제를 DP로 구현 3.2.1. 0-1 배낭 문제 접근 동적 계획법의 조건 최적 하위 구조 (Optimal Substructu.. [Problem] 배낭 문제의 브루트 포스 알고리즘적 접근 (Knapsack, Brute Force) 해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다. 브루트 포스 배낭 (BFKnapsack) 클래스 구현 class BFKnapsack(Knapsack): def get_algorithm(self): return 'Brute Force' def zero_one_solve(self): # TODO: 0-1 배낭 문제 브루트 포스로 구현 3.1.1. 0-1 배낭 문제 접근 $n$ 개의 물체를 배낭에 넣고자 할 때, 가능한 경우의 수는 집합 $A$의 가능한 부분집합의 개수인 $2^n$ 이고, 이는 곧 시간 복잡도가 $O(2^n)$ 임을 의미한다. 기하급수적 복잡도(Exponential Complexity) 를 지닌 해당 접근은 별로 좋지 못하다고 할 수 있다. 구.. [Problem] 배낭 문제 (Knapsack Problem) 1. 개요배낭 문제 (Knapsack Problem)는 최대 수용 무게가 있는 어떤 배낭에 각각의 특정 가치를 갖는 여러 물체를 넣되, 배낭이 지니는 가치가 최대가 되도록 하는 물체의 조합을 찾는 문제를 의미한다.기본적으로 다음을 정의하면,배낭의 최대 수용무게: $W_{ \max }$물체의 집합: $A = \{ a_i | 0 \lt i \le n \}$물체의 개수: $n$$i$ 번째 물체의 무게: $w_i$$i$ 번째 물체의 가치: $v_i$물체: $a_i = (w_i, v_i)$물체 ($a_i$)$a_1$$a_2$$\cdots$$a_n$무게 ($w_i$)$w_1$$w_2$$\cdots$$w_n$가치 ($v_i$)$v_1$$v_2$$\cdots$$v_n$$W_{ \max }$ 만큼 수용할 수 있는 배낭에.. 이전 1 다음
