한 물건을 두 번 넣는 이유는 간단합니다.
DP[i][j+'A의 무게']가 바뀌기 전에 DP[i][j]가 바뀌기 때문입니다.
따라서 다음과 같은 대안들을 생각해볼 수 있겠네요.
1. DP[i]와 길이가 같은 새로운 배열new를 만들고 A를 넣은 방법을 계산해서 new를 전부 갱신한 후에 DP[i]에 new로 대입한다.
2. 물건들의 무게가 전부 양수임을 이용하여, DP[i][j]를 j가 큰 것부터 계산한다.
12865번 - 평범한 배낭
어제도 한시간을 고민해보고 오늘도 고민을 해보고 있지만
이해가 잘 되지 않습니다
DP[i][j+'A의 무게']가 바뀌기 전에 DP[i][j]가 바뀌기 때문입니다.
이 문장이 무슨말씀인지 잘 모르겠습니다.....
저는 DP[I][j-'A의 무게']로 넣어놨는데 혹시 부호가 잘못적힌걸까요
DP[i][j+'A의 무게']가 바뀌기 전에 DP[i][j]가 바뀌기 때문입니다. 라는 말이
Knapsack 알고리즘 이용하여 DP 테이블 채울 때 if j >= W[i] 조건에서
작성하신V[i]+DP[i][j-W[i]] 이부분이
i번째에서 (가방에 넣을 수 있는 최대 무게 - 이번에 넣을 물건의 무게)의 최대 가치를 가져오셨는데
예를 들어서 i가 3, j가 5고 W[1]이 2라고 하면
DP[3][3]에서 i번째 물건을 넣은 경우
DP[3][5]에서는 i번째 물건을 넣고, DP[3][3]에서 i를 넣었는데 한번 더 넣게 되었다는 말 같습니다!
따라서 DP에서 가져올 때 이번에 넣을 물건(i)의 무게가 아니라 이전까지의 최대값(i-1)를 가져와야 할 것같아요
댓글을 작성하려면 로그인해야 합니다.
chanyub1008 4년 전
며칠동안 깔짝대다가 포기하고 오늘 각잡고 두시간반을 고민했는데 못풀겠네요..
앞쪽 질문들 보니까
제가 지금 한 물건을 여러번 담는 상황에 놓인 것 같은데
이걸 어떻게 고치죠..?
4 6
6 13
3 8
7 15
2 6
이렇게 넣었을 때 (3,8)을 두번 담아버리네요..
도저히 머리통돌이가 안돌아갑니다
원래 이게 이렇게 이해가 안되는 파튼가요
오늘 제 암세포들이 암에 걸려 몰살당했습니다..