b_평범한배낭_12865

문제

최대 k무게 넣을수 있을때 최대로 가치있게 즐기고픔

입력
믈픔수, 최대무게
무게 , 가치

답

하나씩 넣는다고하고 생각하면된다..
이제생각할때 물건하나씩 넣는다고생각한다
그리고 이전에 넣은물건이 있는지 무게가 가장큰 dp부터확인을 쭉하고
물건에 넣은 무게가 있으면 거기에다가 현재넣을 물건을 비교해서 최대값을 해당무게가 가진다.
여기서 젤 중요했던것이 무게가 가장 큰 dp부터확인한다이다.
적은 dp부터확인하면 이미더한값에서 또더해서 개수를 중복되게 더해진다.

O(n * k)

import sys

# <span id="n물건-k-limit무게"></span>n:물건, k : limit무게
n, k = map(int,sys.stdin.readline().strip().split())
weight = [] worth = [] # 가치
bag =[0] * (k+1)

# <span id="물건개수만큼-for문-물건을하나씩넣어봣을때의-가치를잼"></span>물건개수만큼 for문 == 물건을하나씩넣어봣을때의 가치를잼
for _ in range(n):
    w, v=map(int,sys.stdin.readline().strip().split())
    if w < k+1:
        for i in range(k+1,0,-1):
            는무게
            if i+w<=k and bag[i] != 0:
                tmpw = i + w
                if tmpw <k+1:
                    bag[tmpw] = max(bag[tmpw],bag[i]+v)
        bag[w] = max(bag[w],v)
        # 처음이면 무적건v갯죵
    # print(w,bag)

print(max(bag))