[모각코] 210714 Today I Learned

백준 #12865 평범한 배낭

 

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

N, K = map(int, input().split())    # 물품의 수, 제한 무게
w = [0]  # 무게
v = [0]  # 가치
for i in range(N):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

f = [[0 for j in range(K+1)] for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, K+1):
        if i == 1:
            if w[i] > j:
                continue
            else:
                f[i][j] = v[i]
        else:
            if w[i] > j:
                f[i][j] = f[i-1][j]
            else:
                f[i][j] = max(v[i]+f[i-1][j-w[i]], f[i-1][j])
print(f[i][j])

 

 

 

0/1 knapsack 문제다. knapsack 문제는 물건을 한 번에 다 넣거나 안 넣거나 2가지 경우만 있다면 동적계획법을, 쪼개서 넣을 수 있다면 greedy 기법을 이용하여 풀 수 있다. 이 문제는 첫 번째 경우로 먼저 최적해의 구조를 파악해야 한다. 크게 두 가지 경우로 나눌 수 있는데, i번째 물건을 넣을 경우, 넣지 않을 경우이다. 둘 중 더 큰 것을 선택해나가면 마지막 f(N, K)에 들어있는 값이 최종 답이 된다.

 

* i번째 물건을 넣을 경우 : f(i, j) = Vi + f(i-1, j-wi)

* i번째 물건을 넣지 않을 경우 : f(i, j) = f(i-1, j)

 

1. 가치를 저장할 2차원 테이블을 만들어준다. (0으로 초기화) 크기 (N+1) * (K+1) 

2. 첫 번째 물건의 경우 물건을 넣는 경우밖에 없기 때문에 무게 j가 첫 번째 물건의 무게 이상이 됐을 때 그 가치를 넣어준다. (안 넣었을 때 대체할 물건이 없음)

3. i번째 물건이 j 무게보다 클 경우 i를 넣지 않는 경우만 있다.

4. j 무게일 때 i번째 물건을 넣을 경우, 넣지 않을 경우를 비교해 더 큰 가치를 넣어준다.

5. 1번 물건, 1 무게부터 차근차근 계산해나가면 마지막 행,열에 있는 값이 최종 답이 된다.

 

 

이차원 테이블을 N*K 크기보다 각각 1씩 더 크게 만들어서 안 될 줄 알았는데 한 번에 맞았다. 알 수 없는 백준 ... N*K 크기로도 인덱스 몇 개 고치면 할 수 있을 거 같긴 한데 이게 더 깔끔한 느낌이라 고치진 않았다. (안 될 수도 있음. 안 해봐서 모름) 크기 하나씩 늘리고 1부터 시작하니까 인덱스 에러도 안 나고 좋다 ㅎㅎ

 

오늘 이상하게 집중이 잘 안 돼서 문제만 몇 개를 옮겨 다녔는지 모르겠다 ,, 토요일엔 집중이 더 잘 됐으면 좋겠다 ㅜ