knapsack(배낭문제) #dp

knapsack(배낭문제) #dp

knapsack(배낭문제) #dp

티스토리툴바

알고리즘/dp

씩씩한 IT블로그 2020. 6. 14. 16:44

배낭문제의 linear seacher는 다음과 같은 코드로 작성할 수 있다.

def maxiValue(volume,index,value):
    global maxForPrune
    if index==N:
        if maxForPrune<value:
            maxForPrune=value
        return 
    #가지치기
    lastValue=0
    for i in range(index+1,N):
        lastValue+=listOfThing[i][1]
    if (value+lastValue<maxForPrune):
        return 

    #고르는경우or안고르는경우
    if volume+listOfThing[index][0]<=K:
        maxiValue(volume+listOfThing[index][0],index+1,value+listOfThing[index][1])
    maxiValue(volume,index+1,value)

ansL=[]

for t in range(int(input())):
    #부피0 가치1
    listOfThing=[]

    N,K=map(int,input().split())
    for i in range(N):
        listOfThing.append(list(map(int,input().split())))
    
    maxForPrune=0
    maxiValue(0,0,0)
    ansL.append(maxForPrune)
    
for t in range(len(ansL)):
    print(f"#{t+1} {ansL[t]}")

item을 선택하는 경우와 선택하지 않는 경우로 나누어 재귀함수를 이용하여 위와같이 작성할 수 있다. 하지만 이는 시간을 많이 소모하는 알고리즘이므로 동적계획법을 이용하여 문제를 해결한다.

<동적계획법>

알고리즘은 아래의 원칙을 따른다.

최대무게제한이 w일때,

1) i-1번째 아이템을 넣을 수 있는 상태에서 최적의 가치와

2) (i번째 아이템을 넣어도 가방이 터지지 않는다는 조건 하에서) i-1번째 아이템까지 넣을 수 있는 상태에서 i번째 아이템을 추가했을때의 가치

를 비교하여 더 큰 값을 찾는 형태로 비교하는것이다. 이를 표로 보이면 이해하기 쉽다.

ex)

먼저 4개의 아이템이 있다고 가정한다. 이때 최대 부피는 5라고 가정한다

item	부피	가치
1	1	2
2	3	2
3	4	4
4	2	3

그러면 아래와 같은 표를 작성할 수 있다.

item행의 의미는 "x번째 아이템을 추가하는 행"으로 이해하면 된다. 즉 item=1인 행은 1번 item을 추가하여 만들수 있는 최상의 가치가 표시되는 것이다.

표를 작성할때는 위에서 언급한 두가지를 고려하여 더 큰값을 선택해 작성하면된다.

첫번째는 1) i-1번째 아이템을 넣을 수 있는 상태에서 최적의 가치 이다

이는 p[i-1][w]로서 작성하려는 셀 바로 윗칸에 해당한다.

두번째는 2) (i번째 아이템을 넣어도 가방이 터지지 않는다는 조건 하에서) i-1번째 아이템까지 넣을 수 있는 상태에서 i번째 아이템을 추가했을때의 가치 이다.

이는 (작성하려는 셀 윗칸에서 추가하려는 아이템의 무게만큼 왼쪽으로 이동한곳에 있는 값) + (추가하려는 아이템의 가치) 에 해당한다.

예를들어 p[1][1]을 작성하기위해선

p[1][0]=0과 p[1][1-(1번 아이템의 부피)]+(1번아이템의 가치) 를 비교해주면 되는것이다.

※이때 p[1][1-(1번 아이템의 부피)] 에서 [1-(1번아이템의 부피)] 값이 음수이면 최대무게를 초과하는경우 이므로 항상 해당값이 양수가 나오는 조건을 추가하여준다

이를 이용하여 표를 완성해주면 아래와 같고 맨끝에 있는 최대무게 5, item4 에서의 최상의가치 6이 구하고자 하는 답이 된다.

이를 코드로 나타내면 다음과 같다.

def knapsack(K,N,listOfThing):
    L=[[0 for col in range(K+1)] for row in range(N+1)]
    for i in range(N+1):
        for j in range(K+1):
            if i==0 or j==0:
                continue
            elif (j-listOfThing[i-1][0])>=0:
                L[i][j]=max(L[i-1][j],L[i-1][j-listOfThing[i-1][0]]+listOfThing[i-1][1])
            else:
                L[i][j]=L[i-1][j]
    return L[N][K]



for t in range(int(input())):
    #N: 물건의 개수, K:최대부피
    N,K=map(int,input().split())


    # [n][0]:부피, [n][1]:가치
    listOfThing=[]
    for i in range(N):
        listOfThing.append(list(map(int,input().split())))
    print(f"#{t+1} {knapsack(K,N,listOfThing)}")

최대무게

item