| 알고리즘의 표현 | 알고리즘의 설계 | 사례 |

사례

■ 배낭문제(Knapsack problem)

  n개의 물건을 배낭에 넣으려고 한다. 각 물건에는 무게 wi와 그 물건을 배낭에 넣었을 때 얻을 수 있는 이익 pi가 연계되어 있다. 배낭에 넣을 수 있는 물건의 최대 무게는 배낭의 용량 M을 넘지 못한다. 또한 어떤 물건의 일부분을 배낭에 넣을 경우 이익 pi의 일부만을 얻게 된다. 아래와 같은 배낭문제에서 얻을 수 있는 최대 이익은 얼마인가?

                n=3, M=10
                (p1,p2,p3) = (20,15,10)
                (w1,w2,w3) = (16,4,2)

  각 물건들의 단위 무게 당 이익이 제일 큰 물건부터 배낭에 넣으면 좋을 것이고, 이들을 계산하면 (20/16,15/4,10/2)가 된다. 따라서 세 번째와 두 번째 물건을 전부 넣고 첫 번째 물건을 4/16만큼 넣으면 30의 이익을 얻게 된다.
  이것은 배낭의 용량을 최대한 적게 사용하면서 최대의 이익을 얻으려는 욕심을 바탕으로 알고리즘을 설계한 것이다. 이와 유사한 경우로 그래프에서 두 노드 사이의 최단경로를 찾을 때, 가능한 거리가 짧은 노드를 거쳐감으로써 최단경로를 구하는 등 여러 문제에 응용되고 있다.