0-1 Kanpsack 알고리즘 문제 모음

0-1 Kanpsack 알고리즘

---

배낭문제: 일정한 가치와 무게가 정해져있는 짐들을 배낭에 담을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제

가방의 가치: value

가방의 무게: weight

최대이윤=dp[n]이라고 할때 

dp[i]=max(dp[i],dp[i-weight]+value)

 

129865 평범한 배낭

n,k=map(int,input().split())
bag=[]
for i in range(n):
  w,v=map(int,input().split())
  bag.append((w,v))
bag.sort(key=lambda x:x[1])

dp = [0]*(k+1)
for w, v in bag:
    for i in range(k, w-1, -1):
        dp[i] = max(dp[i], dp[i-w]+v)
print(dp)

 

1535 안녕

n=int(input())
h=[]
health=list(map(int,input().split()))
happy=list(map(int,input().split()))
for i in range(n):
    h.append((health[i],happy[i]))
h.sort(key=lambda x:-x[1]) # happy 높은 순으로 정렬
# (21,30),(79,25),(1,20)
dp=[0]*101
for health, happy in h:
    for i in range(100,health-1,-1): #100부터 health까지
            dp[i] = max(dp[i], dp[i-health]+happy)
            #i=100~21  dp[i]와 dp[i-21]+30 중 최대값
            #i=100~79  dp[i]와 dp[i-79]+25 중 최대값
            #i=100~1   dp[i]와 dp[i-1]+20 중 최대값
print(dp[99])

 

16493 최대페이지 수

n,m=map(int,input().split())
bag=[]
for i in range(m):
    day,page=map(int,input().split())
    bag.append((day,page))
bag.sort(key=lambda x:-x[1])

dp=[0]*(n+1)
for day,page in bag:
    for i in range(n,day-1,-1):
        dp[i]=max(dp[i],dp[i-day]+page)

print(dp[n])