[코딩테스트][SWEA] 🔥 SWEA 3282번 "0/1 Knapsack" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJAVpqrzQDFAWr

🕒 Python 풀이시간: 30분

def knapsack(k,wt,val,n):
    global dp
    for i in range(n+1):
        for j in range(k+1):
            if i==0 or j==0:
                dp[i][j]=0
            elif wt[i-1]<=j:
                dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]],dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    return dp[n][k]

for tc in range(1,int(input())+1):
    n,k=map(int,input().split())
    wt=[]
    val=[]
    for i in range(n):
        w,v=map(int,input().split())
        wt.append(w)
        val.append(v)
    dp=[[0]*(k+1) for _ in range(n+1)]
    print("#"+str(tc)+" "+str(knapsack(k,wt,val,n)))
    

0/1 Knapsack 문제! 🎒💰

0/1 Knapsack 문제로 다이나믹 프로그래밍을 통해 푸는 문제이다. 기본적인 0/1 Knapsack을 구현할 수 있는지 물어보는 문제이다.

두가지 변수 즉 넣는 물건의 갯수와 해당 무게의 최대치를 기준으로 for문을 돌리면서 dp를 채워나가면 된다. 현재의 dp는 현재의 물건을 넣지 못하는 경우와 넣을 경우로 나누어진다. 만약 현재 기준으로 하는 무게가 전에 물건의 무게보다 작아서 전에 물건을 뺏을 때, 현재의 물건을 넣지 못한다면 현재 물건을 담기 전과 최대 가치가 같기 때문에 dp의 값을 dp[i-1][j]와 똑같이 가져간다.

만약, 만약 전의 물건의 무게를 현재의 물건에서 비웠을 때, 공간의 여유가 있다면 현재의 물건을 넣어서 max값을 갱신한다.

이렇게 Python로 SWEA의 "0/1 Knapsack" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊