(BOJ 12865 평범한 배낭) 0-1 Knapsack DP 시행 착오

[3Aug21] 다시 보니까, '이전 정보 고려 + 앞으로 남은 조각에 대한 답을 반환하는 재귀함수' DP 핵심을 전혀 생각하지 않은 무지성 풀이였네.  종만북좀 공부하고 오니까 뭐가 잘못됐는지 보인다.

 

 

Sol 1) 그리디 - 가성비(가치/무게)가 높은 순으로, 무게 다 찰때까지 차례대로 선택;
기본 예제에서 막힘. 가성비 가장 높은 12 1개가 아니라, 가성비 떨어지는 두 조합 : 8+6을 선택해야 함

---

Sol 2) (WA) DP
dp[i] : 0부터 i번째까지 선택했을 때 (i번째는 무조건 선택), (현재까지의 무게, 가치 합 최대) tuple (i : 1~N)
dp[i] = max(dp[j].val + val[i]) when dp[j].weight + w[i] <= K (j : 1~i-1)

dp[0] = (0,0) 으로 초기화
→ 반례 존재; 0~i번째 까지의 가치 합 '최대' 때문에 문제 생김. 

i번째를 선택할때 무조건 무게가 허용하는 한 넣을 수 있는만큼 물건 넣어서 최대 가치 만들어냈을 때를 (무게, 가치) 로 저장함. 물건을 '덜 넣는' 선택지가 없었음  

i번째를 선택했을 때 가치 합이 반드시 최대가 아니어도 됨.
지금 덜 선택하고, 나중에 더 좋은 걸 선택하는게 Global optimum이 될 수도 있으니까

 

(왜 틀렸는지 반례 생각해보느라 시간 많이 씀. 

DP 문제에서 '최선의 선택'을 기록하느냐, 아니면 그렇지 않은 선택도 기록하느냐를 잘 구분) 

---

Sol 3) DP
dp[i][w] : i번째 까지 선택해서 (i번째는 선택할수도 안할수도) 무게가 w일때 최대 가치

→ Q. 아까와 다른 점? i번째 선택지까지 왔을 때, 무게별로 최대 가치를 저장함.
Sol 2는 최대 가치와 함께, 그 최대 가치를 만드는 무게를 같이 저장했었음 (즉, 다른 선택지가 없었다)

i번째 선택 : dp[i][w+inp_w] = dp[i-1][w] + inp_v (단, w+inp_w <= K)
선택 X : dp[i][w] = max(dp[i][w], dp[i-1][w])
(선택한 것과 겹치는 경우, 더 큰 val 값 선택)

dp[0][0] = 0으로 초기화; 나머지는 다 -1로 두기

=> i번째의 선택지까지, 각 weight status마다 최선의 선택지만 남겨뒀다고 생각하면 편함.

(해당 weight를 만들기 위해 선택할 수 있는 배낭 조합 중, 최대 가치를 가지는 조합)

잘 안와닿으면 Optimal substructure의 관점에서 생각.
i-1번째 물건을 선택해서 무게가 W가 될때 최적해가 구해져있다고 하자.
i번째 물건을 선택해서 W+weight[i] 무게를 만드는 경우, W의 최적해 (dp[i-1][W])에 val[i]를 더함으로써 새로운 최적해 (dp[i][W+weight[i]) 찾기 가능
선택하지 않는 경우는, i-1번째에서 구한 최적해를 그대로 들고와서 최적해로 쓰면 된다.

 

dp 정의에 따라, 우리가 구해야 하는 답은 dp[N] 배열 중 최댓값.

 

N, K = map(int, input().split())
dp = [[-1 for _ in range(K+1)] for _ in range(N+1)]

dp[0][0] = 0
for i in range(1, N+1):
    inp_w, inp_v = map(int, input().split())
    for w in range(K+1):
        if dp[i-1][w] != -1: # 안 건들인 초기화 상태면 패스
            if w + inp_w <= K:
                dp[i][w+inp_w] = dp[i-1][w] + inp_v
            dp[i][w] = max(dp[i][w], dp[i-1][w])

print(max(dp[N]))

-1로 표시된 부분 : 저 무게는 현재 물건 조합으로 만들 수 없다는 의미.

Sol 4) DP (보통 0-1 Knapsack의 정해로 소개됨)
dp[i][w] : i번째 까지 선택 (i는 선택할수도, 안할수도), 배낭 제한 w일때 최대 가치

Sol 3이랑 점화식 동일. 사실상 같은 풀이인데, 여기선 초기화를 -1로 안하고, 배열을 전부 다 채워넣음.

 

dp[0]을 모두 0으로 초기화 하고, 답도 dp[N][K]로 정확히 구해짐

 

 

gsmesie692.tistory.com/113

Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)

---

배운점

DP 반례를 통한 공부 : DP 문제에서 '최선의 선택'을 기록하느냐, 아니면 그렇지 않은 선택도 기록하느냐