같은 물건을 여러 개 넣을 수 있다고 하고, 입력이 다음과 같다고 합시다.
2 10
6 5
5 3
이러면 0번 물건은 안 넣고 1번 물건을 2개 넣는 게 정답이겠죠.
j가 w[i]부터 증가할 경우
i=0이 끝난 후 dp 배열의 모습
0 0 0 0 0 0 5 5 5 5 5
i=1이 끝난 후 dp 배열의 모습
0 0 0 0 0 3 5 5 5 5 6
j가 k부터 감소할 경우
i=0이 끝난 후 dp 배열의 모습
0 0 0 0 0 0 5 5 5 5 5
i=1이 끝난 후 dp 배열의 모습
0 0 0 0 0 3 5 5 5 5 5
직접 dp를 계산해보면서 두 가지 경우를 비교해보시면 쉽게 이해하실 수 있을 겁니다.
이 상황을 탑다운 vs 바텀업이라고 부를 수 있을 것 같긴 한데 상당히 단순한 예시가 되겠네요.
ijyuuu 2년 전
해당문제는 각 물품의 개수가 1개로 제한되어서 다음과 같이 풀었는데
for i in range(n): for j in range(k, w[i]-1, -1): dp[j] = max(dp[j-w[i]] + v[i], dp[j])만약 물품의 개수가 무제한이라면 다음과 같이 풀어야하더라구요
for i in range(n): for j in range(w[i],k+1): dp[j] = max(dp[j-w[i]] + v[i], dp[j]혹시 j가 거꾸로 돌고 안돌고의 차이가 무엇인지 알려주실수있나요?
그리고 이게 탑다운과 바텀업의 차이인지 알고싶습니다 ㅠㅠ