동적계획법6

knapsack

-n개의 아이템과 배낭

-각각의 아이템은 무게 W(i)와 가격 V(i)를 가짐

-배낭의 용량 w

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

Greedy 

-가격이 높은것부터 선택

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

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

 

동적계획법을 사용해서 이 문제를 풀어야한다.

동적계획법을 사용하기 위해서 먼저 순환식을 세워야함

여기서 OTP(i,w)는 배낭용량이 w일때 아이템 1,2,...i로 얻을 수 있는 최대 이득을 뜻함

 

현재 잔여 용량 w가 아이템 i의 무게 wi보다 커야한다. 이러한 조건이 만족될 경우에만 2를 선택할수 있다.

 

 

2차원 배열을 사용해서 표현되므로 2개의 반복문이 사용된다.

 

Knapsack의 시간복잡도

-O(nW)의 시간 소요

-다항 시간인가의 여부( 다항 시간이라는 것은 입력크기에 대한 다항함수일 때 성립)