12865 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

#12865 평범한 배낭 정리

#1
'''
음 dp에 v를 저장하는게 좋을듯 v 자체의 값이 최대여야 되니깐..
처음 설정은 -1 로 해놓고 탐색하면 0 무게만 인덱스로 놓기에는 넣다 뺏다도 해야되고 중복되도 안된다.
고로 몇번째 물건을 보냐로 순서대로 해놓고 이전꺼로 탐색하는데 전의 무게랑 지금 보는 무게 더해도 안 넘으면 넣기 이런거 하면 될듯
'''

import sys
input=sys.stdin.readline

#스탠다드 인풋

n,k=map(int,input().split())
#n,k 입력

dp=[[-1 for i in range(k+1)] for i in range(n)]
#visited를 포함한 ( -1을 초기값으로 설정) dp 생성)

 

weight,value=[],[]
#weight value 리스트 생성

for i in range(n):
    w,v=map(int,input().split())
    if w>k:
        n-=1
        continue
    weight.append(w)
    value.append(v)

#물건을 받으면 weight value 에 하나씩 넣는데 만약 weight가 하나만 해도 최대무게를 넘어버린다면 n만 깎고 #continue한다.

 

if weight:
    dp[0][weight[0]]=value[0] 
    for i in range(1,n):
        dp[i][weight[i]]=max(dp[i-1][weight[i]],value[i])
        for j in range(k+1):
            dp[i][j]=max(dp[i-1][j],dp[i][j])
            if dp[i-1][j]!=-1 and j+weight[i]<=k:
                dp[i][j+weight[i]]=max(dp[i-1][j+weight[i]],dp[i-1][j]+value[i])
    print(max(dp[n-1]))
else:
    print(0)

 

#weight에 뭐라도 들었다면, 무게가 안 넘어가는게 있어서 머가 담겼다면 알고리즘을 돌리는데, 간단하게 말하자면 이전#꺼와 비교해서 크면 갱신 안크면 그대로 반복하는 것이다.

 

#돌아가긴 하는데 시간이 너무 오래 걸렸다. 내가 볼땐 알고리즘 자체는 문제가 없으나 구현에 문제가 있는 것 같았다. 그리고 찾아본 결과 진짜 그러했다...ㅠㅠ

#2
from sys import stdin
input = stdin.readline
#스탠다드 인풋

def dp(N,K):
    D = {0:0}
    for _ in range(N):
        w,c = map(int, input().split())
        tmp = {}
        for dw,dc in D.items():
            neww = w+dw; newc = c+dc
            if neww <= K and newc > D.get(neww,0):
                tmp[neww] = newc
        D.update(tmp)
    
    return max(D.values())

N,K = map(int, input().split())
D = dp(N,K)
print(D)

 

#여기서 알아야 할 개념 (dict:사전 함수) (items: dict에 있는 key:value를 합쳐서 표현) (values: 모든 value를 가져옴)      # (update: dict를 서로 합침) 이정도를 알고 있으면 위에 있는 알고리즘으로 돌릴 수 있게 된다. 여기서 시간이 줄어드는 # 점은 list로 만든 dp는 모든 인덱스를 돌아서 비로소 가게 되는데 dict로 만든거는 그 숫자만 딱딱 움직일 수 있게 된   #다. 이것만으로 무려 7000ms을 절약하게 되었다.....