Dynamic Programming-knapsack problem

knapsack problem

- n개의 아이템과 배낭

- 각각의 아이템은 무게 Wi와 Vi를 가짐

- 배낭의 용량 W

- 목적 : 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합

예

Greedy

- 가격이 높은 것부터 선택

- 무게가 가벼운 것부터 선택

- 단위 무게당 가격이 높은것부터 선택

->불가능

순환식

bottom-up