troyeagles   1년 전

제 의견이 틀린건지 모르겠는데 한번 글 올려봅니다.

문제에서

"준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자."

무게의 합이 k 이하인 경우 중에서 가치의 최댓값을 구하라는 건데요.

제 dp 코드에서 dp[i]는 정확히 무게의 합이 i인 경우 중 가치의 최댓값 입니다. (아래 코드 참고)

그런데 출력 부분에서 두가지 모두 정답처리 되더라고요

1. cout<<dp[k]; -> 정확히 무게의 합이 k인 경우를 출력함

2. cout<<max_element(dp, dp+k+1); -> 무게가 k이하인 모든 경우 중 최댓값을 출력함

제 생각에는 1의 경우는 문제에 맞지 않는 것 같은데, 정답 처리되는군요.

제가 틀렸다면 이유를 말씀해 주시면 감사하겠고,

1번 경우는 오답 처리 되어야 했었다면 무게가 k이하인 경우가 최대가 되는 테스트케이스를 추가해 주세요.

1번 경우 제출번호: 93863223       -오답 처리되어야 한다고 생각, but 정답 처리됨

2번 경우 제출번호: 93863247

만일 틀린게 맞다면 https://www.acmicpc.net/proble... (평범한 배낭 2) 도 테스트케이스를 추가해야 할 것 같습니다. (같은 이유)

감사합니다.

zenith82114   1년 전

아니요, 지금 푸신 코드에서 dp[i]는 무게의 합이 정확히 i가 아니라 i 이하일 때 최대 가치입니다. "정확히 i"로 정의하고 싶다면 dp 배열 초기화를 dp[0] = 0, dp[1 이상]은 모두 $-\infty$으로 해야 합니다. 이렇게 하면 출력 파트에서 말씀하신 대로 dp[0] ~ dp[k] 중 최대를 취해야 옳은 답이 나올 것입니다.

troyeagles   1년 전

@zenith82114

답변 주셔서 감사합니다. 그런데 dp[j] 에 dp[j-1]을 그대로 취해 주는게 없고 정확히 j가 되도록 하니까 dp[i] 가 정확히 i 인 경우의 최댓값을 뜻하는 게 아닐까요?

그리고 dp[1이상]을 무한으로 초기화해야 한다고 하셨는데 그렇다면 최댓값이 무조건 무한이 아닐까요? (for문에서 max 쓰니까)

제가 오해하고 있는 거라면 더 자세한 설명을 부탁드려도 될까요?

zenith82114   1년 전

  • (A) $i$ 이하로 정의하는 경우
  • (B) 정확히 $i$로 정의하는 경우

(A), (B) 중 어느 쪽을 쓰든 dp[j]=max(dp[j], dp[j-w[i]]+v[i])라는 점화식은 동일하게 나옵니다.

달라지는 것은 dp 배열의 초기화입니다. 처음에 아직 물건을 넣지 않았을 때 (무게 합이 0일 때) 가치 합이 0보다 크기는 불가능하기 때문에 (A)로 풀 경우 dp는 전부 0으로 차 있어야 하며, (B)로 풀 경우 dp[0]만 0, dp[1 이상]은 모두 마이너스 무한대(위 댓글을 다시 봐 주세요)로 놓아서 아예 존재하지 않는 상태로 만들어야 합니다.

troyeagles   1년 전

@zenith82114

감사합니다!

-INF 부분은 제가 잘못 보았습니다..^^

말씀해주신 대로 코드를 짜서 넣어본 결과 그렇게 나오네요.

많이 부족한 제 질문에 답변해 주셔서 감사합니다.


감사합니다!

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