[백준 12865] 평범한 배낭

 

 

 

---

 

무게(w)	6	4	3	5
가치(v)	13	8	6	12

thing

n(물건갯수) : 4

k(최대용량) : 7

 

=> 최대용량(k)를 넘지 않게, 가장 가치의 합이 높도록 물건을 넣기

 

현재물건의 남은 허용 용량(j)보다 이번에 넣을 물건 무게가 크다면 안넣음

case1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다.

case2)  현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다.

 

이후, max값을 이용해 어떤 것의 가치가 더 큰지 확인

결론적으로 테이블d에 더 큰 숫자가 있는 칸의 숫자 출력 

 

d: 최대가치, 테이블 / thing: 물건, 가치를 저장해둔 리스트 

		0	1	2	3	4	5	6	7
w	v
6	13		0	0	0	0	0	13	13
4	8		0	0	0	8	8	13	13
3	6		0	0	6	8	8	13	14
5	12		0	0	6	8	12	13	14

테이블 d

---

 

n, k = map(int, input().split())#n=물건갯수, k=최대용량

thing = [[0,0]]#물건정보 저장할 리스트 초기화
d = [[0]*(k+1) for _ in range(n+1)]#테이블 초기화

for i in range(n):#입력된 n갯수만큼 for문
    thing.append(list(map(int, input().split())))#append:w와v 입력받아 thing리스트에 추가

for i in range(1, n+1):#원래는 0부터인데 물건 무조건 넣을 거니깐 1부터, n+1은 0부터 시작하니깐 
    for j in range(1, k+1):#j는 현재 배낭에 넣을 수 있는 용량
        w = thing[i][0]#0번째 행
        v = thing[i][1]#1번째 행

        if j < w:#j는 더 담을 수 있는 허용용량
            d[i][j] = d[i-1][j]#담기 이전으로 돌아감
        else:
            d[i][j] = max(d[i-1][j], d[i-1][j-w]+v)#전에 거랑 이번 물건의 가치 비교해서 더 큰 가치를 선택함

print(d[n][k])

 

 

---

어렵당 방탈출 첨 하는 느낌

피드백 환영 빠위우이윙ㅇㅇㅇ