[알고리즘] 0-1 Knapsack Problem

흐짜짜! 🫒 올리브·2020년 11월 29일
1

알고리즘

목록 보기
1/1
post-thumbnail

몰랐다!나는 몰랐다!
생애 첫 코딩테스트를 보고 나니 느끼는 것들

  • 나 알고리즘 공부 제대로 안했다 호호
  • 왠지 내장 함수가 있는 python이 c보다 빨리 할 수 있을 것 같다
  • 하지만 난 python을 잘 모른다
  • 3시간 버티기 제법 힘들ㄷ..

그러니까 공부 대충하지 말자...

고등학교 때 써본 게 마지막이었던 python을 꺼내보자...
물론 문제를 빨리 푸는 게 목적이라 python을 꺼내보는 것 뿐만은 아니고, C만 사용할 줄 안다는 것이 나의 확장성 에 조금 부끄러움을 느꼈기 땜문

하지만 python 1도 기억안나..
설치부터

  • pyhton idle ; 불편..안 익숙..

하지만! 두둥!
더 좋은 게 있었다! 두둥!

친구덜이 쓰는 게 뭔가 했더니 vs code였다.. 이제 깨달았어!
역시 나는 비전공생이라 할 만 하구먄 콜록


Knapsack Problem

n개의 item이 있다
각 item의 무게(weight)는 wi, 이득(profit)은 pi
가방에 최대한 넣을 수 있는 무게는 W
W를 넘지 않으면서 이득(profit)을 최대화하려면 각 item을 넣을까(1)/말까(0) 결정해야 한다!
*이 때 만약 item을 쪼개서 넣을 수 있다면 Fractional Knapsack Problem!
그렇지 않다면 0-1 Knapsack Problem!

*참고
설명이 훌륭한 선생님 블로그
boj 평범한 배낭

먼저, DP(dynamic programming)이란

Dynamic Programming

table을 만들어 작은 문제들의 계산값을 기억하며, 그 값을 이용해 간단한- 시간 내에 큰 문제들의 계산을 하려고 하는 것!

참고

DP로 풀 수 있는가

DP로 풀 수 있는지는 Principle of Optimality가 성립하는지 보면 된다.

Principle of Optimality
어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.

라고 블로그 선생님께서는 첨부해두셨다
교과서에는

Principle of Optimality
The Principle of Optimality is said to be applicable to a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.

결국

큰 문제의 해가 최적(optimal)이다~ 라고 하면 작은 문제의 해도 최적이다~

라고 할 수 있으면 principle of optimality가 성립한다는 거다!

오호
그럼 0-1 Knapsack Problem은 Principle of optimality를 성립하는지 어떻게 알 수 있을까? 증-명해보면 된다.
(생략)

그럼 "큰" 문제들은 "작은" 문제들을 가지고 어떻게 풀 수 있을까
어떻게 반복되는지 확인하면 된다. (점화식 찾기)

점화식

i번째 item을 일단 넣을 수 있는가? 들어가긴 함?

  • 들어가긴 함
    • 이득이 늘어나니까 넣어야지
    • 얘 안 넣는 게 낫겠다
  • 안 들어감

이런 경우의 수가 있다.

그러면 각 경우의 수에서는 어떤 것을 선택해야 할까

(w는 total weight 0 < w <= W, P[i][w]는 i번째까지 item 고려 시 무게 한도 w일 때 optimal profit)

  • 들어가긴 함 : wi <= w
    • 이득 늘어나니까 넣어야지 : P[i-1][w-wi] + pi
    • 얘 안 넣는 게 낫겠다 : P[i-1][w]
  • 안 들어감 : wi > w : P[i-1][w]

그렇다면 들어가긴 할 때, 둘 중의 최적 optimal은 누구인가
바로, max값! 이득이 최대가 되어야 하니까!

그래서 P[i][w]의 점화식은 이렇다.

P[i][w]
if wi <= w : max( P[i-1][w-wi] + pi , P[i-1][w])
else : P[i-1][w]

이제 작은 문제로 큰 문제를 풀 수 있는 점화식이 완성되었으니 table을 만들어 작은 문제의 해부터 채워보자.

table

(생략)
.
.
.

code

import sys

def knapsack(W, wt, val, n): #W 무게 한도, wt 각 보석 무게, val 각 보석 가격, n 보석 수
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0;
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1]+K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
            #print(K[i][w], end=' ')
        #print('\n')
    return K[n][W]

wt = []
val = []
N,K = map(int,sys.stdin.readline().strip().split())
for i in range(N):
    w,v = map(int, sys.stdin.readline().strip().split())
    wt.append(w)
    val.append(v)
print(knapsack(K,wt, val, N))

끄-덕
이 와중에 알게된 python 지식

#map function
map(<function> , <iterable>)     *iterable : list, tuple, dictionary, str)
map(int, a) : a를 int형으로
list(map(mul,a)) : list 요소에 3씩 곱해주기
#split function
a.split()
공백으로 나누기
a,b,c = map(int, input().split())   *input은 속도가 느리다
#strip function
rstrip() : right 공백 제거(\n 제거)
lstrip() : left 공백 제거
strip() : 양쪽 공백 제거
#print function
print(,end' ') 공백으로 구분하여 가로로 출력
max(a,b)
min(a,b)

python에는 c처럼 if(a>b) max = a; else max = b;
해 줄 필요 없이 내장 함수가 있다...!

0개의 댓글