ggb05224   1년 전

질문이 이상해도 이해 부탁드립니다... 

(기본적인 DP 개념을 알고 있다는 가정하에)

table[k][W] : k개의 물건을 버틸 수 있는 무게가 W인 배낭에 넣을 때 최대가치

기본적으로 table을 차례대로 채우기 위해 경우의 수를 나눌때

먼저 

1. 넣고자 하는 물건이 배낭용량보다 클때

2. 넣고자 하는 물건이 배낭용량 보다 작을 때로 나눈다음

만약 넣고자 하는 물건이 배낭용량 보다 작다면

다시 

2-1 넣을 경우와

2-2 넣지 않을 경우로 

나눈다고 알고 있습니다

하지만 여기서 가치를 최대로하기 위해서는 무조건 넣는게 더 큰 가치를 얻을 수 있는게 아닌가라고 생각했고 이게 아닌 이유가 납득이 되지 않아서 질문드립니다

만약 2-2 넣지 않을 경우에서 더 큰 가치를 얻을 수 있는 경우가 있다면 어떤 상황일 까요 ㅜㅜ

고수님들 부탁드립니다.

peydihalta   1년 전

같은 8kg를 넣어도

가치가 1인 4kg짜리 물건을 2개 넣을 수 있고

가치가 5인 8kg짜리 물건을 1개 넣을 수도 있습니다.

8kg짜리 가방에 4kg짜리를 먼저 넣게 되면 8kg짜리를 못 넣습니다.

ggb05224   1년 전

감사합니다 

table 채워 넣는 과정에서 잘못 이해하고 있었던 부분이 있었습니다.. ㅜ



댓글을 작성하려면 로그인해야 합니다.