[Python][SWEA] 3282. 0/1 Knapsack D3

SW Expert Academy

---

🗒️파이썬 코드 풀이

def dp(N,K) :
    dp_lst = [[0] * (K+1 ) for _ in range(N+1)] # dp 2차원 행령
    for n in range(N+1):  # 최대 개수와 최대 부피로 이뤄진 2차원 행렬
        for k in range(K+1):
            if n==0 or k==0 : 
                dp_lst[n][k] == 0 
            elif V_lst[n-1] <= k :
                dp_lst[n][k] = max(C_lst[n-1]+dp_lst[n-1][k-V_lst[n-1]], dp_lst[n-1][k])
            else : 
                dp_lst[n][k] = dp_lst[n-1][k]
    return dp_lst
 
T = int(input())
for tc in range(1,T+1) :
    N,K = map(int,input().split()) # N은 물건 개수 / K는 최대 부피
    V_lst = [] # 부피 리스트
    C_lst = [] # 가치 리스트
    for _ in range(N) :  
        v,c = map(int,input().split())
        V_lst.append(v)
        C_lst.append(c)

    ans = dp(N,K)
    print(f"#{tc} {ans[N][K]}")

 

1. N의 범위가 100이하로 DP를 생각해준다. 

 

2. 2차원 리스트에서 행은 N(물건 개수) 열은 K(물건 부피)로 하고 값은  C(물건 가치)로 한다.

 

3. DP 리스트를 N+1, K+1 크기로 만들어준다.

 

4. 

(1) :  0행 또는 0열 dp_lst의 값은 모두 0 

 

(2) :  0~K 까지의 수를 반복하는 k 값이 V_lst (현재 인덱스 부피)보다 같거나 클 경우  -> 

C_lst (현재 인덱스 가치) + dp_lst[n-1][k-V_lst[n-1]] (현재  dp_lst 위치에서 한칸 위에서 왼쪽 끝 부터 계산) 과 

dp_lst[n-1][k]  (현재 dp_lst 한칸 바로 위) 와  크기 비교 

 

(3) : dp_lst[n-1][k]  (현재 dp_lst 한칸 바로 위)

 

5. dp_lst를 리턴하여 원하는 값 출력

 

N \ K	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	2	2	4	4
3	0	2	2	2	4	6
4	0	2	3	5	5	6

 

🚨 생각 오류

def dfs(n,v,c) :
    global maxc 

    if v > K : 
        return 
    if n == N : 
        maxc = max(maxc,c)
        return 

    dfs(n+1, v, c)
    dfs(n+1, v + lst[n][0], c + lst[n][1])

T = int(input())
for tc in range(1,T+1) :
    N,K = list(map(int,input().split()))
    lst = [list(map(int,input().split())) for _ in range(N)]
    
    maxc = 0
    dfs(0,0,0)
    print(f"#{tc} {maxc}")

 

완전탐색으로 물건을 선택했을 경우와 선택하지 않았을 경우로 풀었다.

문제가 풀어는 지는데, 제한시간 초과로 pass하지는 못했다. 

(N의 크기를 보지않고 전략을 구성했다...)

 

🧐 내 생각 정리

dp는 점화식만 잘 하면 된다는데... 비슷한 문제로 swea에 햄버거 문제가 있다.

거기에서는 완전탐색으로 풀어서 이것도 쉽겠지 생각했다가, 하루종일 이해도 못하고 멘탈 와장창 깨진 문제이다. 

특히 dp 2차원 리스트를 구성하는 단계가 너무 이해가 안됐다...

저 코드가 이해가 안된다면, 직접 하나하나 계산해서 dp 행렬을 만들어보자.  

그렇게 하면 왜 저렇게 써야하는지 이해가 될 것이다.  dp 리스트 구현은 외워두자 ^o^ 

---

📚문제

민수에게는 1번부터 N번까지의 번호가 부여된 N(1≤N≤100)개의 물건과 최대 K(1≤K≤1000) 부피만큼을 넣을 수 있는 가방이 있다.

1번 물건부터 N번 물건 각각은 부피  Vi와 가치 Ci 를 가지고 있다. (1≤Vi, Ci≤100)

민수는 물건들 중 몇 개를 선택하여 가방에 넣어서 그 가치의 합을 최대화하려고 한다.

단, 선택한 물건들의 부피 합이 K 이하여야 한다.

민수가 가방에 담을 수 있는 최대 가치를 계산하자.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에 물건의 개수와 가방의 부피인 N K가 주어진다.

다음 N개의 줄에 걸쳐서 i번 물건의 정보를 나타내는 부피  Vi와 가치 Ci가 주어진다.

[출력]

각 테스트 케이스마다 가방에 담을 수 있는 최대 가치를 출력한다.