[B]BOJ12920 knapsack2, dp 뿌수기

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

1트

https://cpusuite.blogspot.com/2025/04/bboj12865-knapsack-dp.html와 동일하게

최대의 만족도를 도출하는 문제이지만 물건에 재고 attribute가 추가되었다.

한 행에 weight : 3, value : 5, stock: 3를 입력받으면

그 물건의 재고가 3개 있다는 뜻이다.

weight 3 , value 5, stock 3은

weight 3 , value 5

weight 3 , value 5

weight 3 , value 5과 같지 않을까?

대신 물건의 개수가 2개 늘어나며

테이블의 크기도 늘어나며
이는 런타임 상에서 재고 수 만큼 메모리를 더 차지한다.

dp_table

column = weight

row = 까지 살펴본 물건 번호.

ex) row =4 라면, 4번 물건까지 살펴봤다는 상태를 의미

관계식

dp_table[n][w] = w 이하의 무게로 n번째 물건까지 살펴봤을 때의 최대 가치값.

 

참조 후보 1

1. dp_table[n][w]= dp_table[n-1][w]
w 이하의 무게로 n-1번째 물건까지 살펴봤을 때의 최대 가치값.

예를 들어, 

dp_table[8][10]을 구하려고

dp_table[7][10]을 참조했을 때의 상태는

7번까지 살펴보고 무게가 이미 10인 상태이다.

8번까지 살펴본 후에도 dp_table[7][10]이 최대 가치값이라면

이 값을 사용할 수 있다.

참조 후보 2

2. dp_table[n][w] = dp_table[n-1][w-w8] + v8

예를 들어,
7이 아닌 8번 물건을 넣음으로서 최대가 되는 경우.

dp_table[n-1][w - 8번물건의 무게] + 8번 물건의 가치값

관계식

위 두 후보 중에 더 가치값이 큰 하나를 선택하는

dp_table[n][w] = max(dp_table[n-1][w], dp_table[n-1][w-wj] + vj)

코드가 물건을 고를지 말지 TF 마킹을 하면서, 더 큰 가치 값을 갱신하는 역할을 한다. 

동일한 물건이 있어도

Item의 각 동일한 물건 개수만큼 리스트를 늘리고

dp 테이블 크기를 늘리면 dp 로직은 바꾸지 않아도 된다고 생각했다.

결과

예제 input/output은 통과했는데

메모리 초과가 떠버렸다 

기존 dp table은 그대로 사용하면서

재고 조건을 고려해야한다.

  

2트

연구중