codingismylife   1년 전

DP[N][K] : 물건을 N번까지 살펴보고, 무게가 K일 때의 최대 가치로 정해서 문제를 풀었습니다. 

2차원 DP로 푸신 다른 분들 보니까 답을 구할 때 그냥 DP[물건의 개수][최대 무게]에 저장된 값을 그냥 반환하셨는데, 


경우에 따라서 배낭의 최대 용량보다 적게 들어갔을 때(예를 들어 배낭의 무게가 15인데 아무리 해도 합이 15가 되지 않는 경우)도 답이 될 수 있다고 생각해서 DP[N][i] 중에서 (i는 처음부터 배낭의 MAX용량까지) 최대값을 구해서 반환하도록 했는데, 이렇게 하면 비효율적인가요??

손으로도 직접 써가면서 경우의 수를 봤는데, 잘 모르겠습니다 ㅠㅠ

skuru   1년 전

작성하신 코드에서 dp[i][j]는 i번째 물건까지 고려했을 때 가방에 담은 무게가 j이하인 최대 가치인 것으로 보입니다. 따라서 dp[N][K]를 출력해도 맞습니다.

그래서 30번째 식에서 dp[i - 1][j - x] + y를 고려할 때 (i - 1번째 물건까지 고려하여 가치가 j - x인 경우)가 존재하는지 검증하지 않아도 되는 것입니다.

예를 들자면 i=1일 때 dp[i - 1][j]는 모두 0이므로 x <= j인 j에 대해 dp[1][j]는 모두 y가 됩니다.

codingismylife   1년 전

감사합니다!! 변수 정의를 잘 해야겠네요 ㅠㅠ

leeingyun96   1년 전

라인 25에서 전부 순회를 하기 때문에 "무게 0, 가치 0에 물건 1을 더한다"뿐만 아니라 "무게 3(이때 3짜리 dummy가 채워져있음), 가치 0에 물건 1을 더한다"도 시행되기 때문에 "dp[i][j]는 i번째 물건까지 고려했을 때 가방에 담은 무게가 j이하인 최대 가치인 것으로 보입니다"가 되는 것으로 보입니다.

 

의도하신 대로 하시려면 dp[0][0]=0이고 나머지는 null로 채우신 뒤 라인 25를 null이 아니라면을 조건을 걸면 될 것 같습니다.

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