akwk777   4년 전

알려조잉~~

배낭의 최대 무게가 올라가면서  물건의 무게를 최대무게에서 빼나가며 dp테이블을 채우는 방식으로 하고있습니다.

중간에 빼먹는건지 먼지... ㅠㅠ

pichulia   4년 전

check라는 배열을 통해서 지금까지 사용한 짐들의 목록을 관리하는건

굉~~~~~~~~~~~장히 신뢰도가 떨어지는 작업입니다.

뭐라 설명하기 힘든데... 예를 들어 1, 2, 3 번 짐을 사용해서 무게 20을 채운거랑 4, 5, 6번 짐을 사용해서 무게 20을 채운거는 가치가 같을지언정 다르게 봐야합니다.

똑같은 20이라는 무게에 가치도 똑같을지라도, 미래에 넣을 짐들이 달라지기 때문입니다.


이렇게 풀이에 논리적으로 오류가 있는 경우는 N이나 K가 작은 경우에도 랜덤데이터로 반례가 쉽게 나오는 특징이 있습니다.

아래는 제가 만든 랜덤데이터로 만든 반례들 목록의 일부입니다. (혹시나 K가 너무 작아서! 혹은 W값이 같은 물건들이 있는걸 고려 안한게 문제였어! 라고 잘못 생각하실까봐, V도 적당히 크고 W가 다 다르면서 N도 적당히 작은 예제를 제일 위에 올려드렸습니다ㅋ)취향껏 사용하시면 됩니다.

데이터는 각 케이스마다 

wrong! [정답] != [오답]

[N] [K]

[W[1]] [V[1]]

...

포멧으로 작성되있습니다.

akwk777   4년 전

아 그렇군요!

답변 정말 감사합니다 ㅠㅠ 이렇게 잘 알려주실줄이야

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