mojo's Blog

0-1 Knapsack Example 2: n = 6, W = 10 알고리즘 별로 획득되는 이익이 다른것을 알 수 있다. 위 예제에서 그나마 좋은 알고리즘이 greedy 알고리즘인데 이 중에 최대 이익을 뽑아낼 수 있는 알고리즘을 활용하여 O(nlogn) 의 효율을 뽑아서 이익을 뽑도록 한다. The Greedy Methods A technique to follow the problem-solving heuristic of making the locally optimal choice at each stage. ※ Strategy - 매 순간마다 가장 최선인 것을 선택하는 방법이다. - 즉, locally optimal를 선택함으로써 globally optimal을 도달하려는 것이 궁극적인 목표이다. ※ ..

0-1 Knapsack Problem 에 대한 고찰 이전에 0-1 Knapsack Problem에 대해서 Input 을 고려할 때, 물건의 갯수 n과 최대로 챙겨오기 위한 무게 W에 대해서 시간복잡도가 O(nW) 가 나왔다. 이는 Polynoimal time algorithm 즉, "P에 속한 알고리즘일까?" 라는 생각을 해봐야 한다. 이전에 했던걸 예로 들면 n = 6, W = 10이므로 n * W = 60 번만에 최대 이익을 낼 수 있었다. 그렇다면 다음과 같은 극적인 상황을 고려해보자. Profit은 고려하지 말고 weight만 살펴보도록 하자. 80M 즉, 8 * 10^7 의 weight 을 가지고 있으며 최대로 챙겨올 수 있는 무게가 만약 100M 이라고 한다면 W = 10^8, 즉 6개의 op..