chanyub1008   4년 전

며칠동안 깔짝대다가 포기하고 오늘 각잡고 두시간반을 고민했는데 못풀겠네요..

앞쪽 질문들 보니까

제가 지금 한 물건을 여러번 담는 상황에 놓인 것 같은데

이걸 어떻게 고치죠..?

4 6

6 13

3 8

7 15

2 6

이렇게 넣었을 때 (3,8)을 두번 담아버리네요..

도저히 머리통돌이가 안돌아갑니다

원래 이게 이렇게 이해가 안되는 파튼가요

오늘 제 암세포들이 암에 걸려 몰살당했습니다..

wider93   4년 전

한 물건을 두 번 넣는 이유는 간단합니다.

DP[i][j+'A의 무게']가 바뀌기 전에 DP[i][j]가 바뀌기 때문입니다.


따라서 다음과 같은 대안들을 생각해볼 수 있겠네요.


1. DP[i]와 길이가 같은 새로운 배열new를 만들고 A를 넣은 방법을 계산해서 new를 전부 갱신한 후에 DP[i]에 new로 대입한다.

2. 물건들의 무게가 전부 양수임을 이용하여, DP[i][j]를 j가 큰 것부터 계산한다.

chanyub1008   4년 전

어제도 한시간을 고민해보고 오늘도 고민을 해보고 있지만

이해가 잘 되지 않습니다

DP[i][j+'A의 무게']가 바뀌기 전에 DP[i][j]가 바뀌기 때문입니다.

이 문장이 무슨말씀인지 잘 모르겠습니다.....

저는 DP[I][j-'A의 무게']로 넣어놨는데 혹시 부호가 잘못적힌걸까요

wider93   4년 전

구체적인 수치를 넣어서 무게 10짜리 물건이 끼어있다고 할게요. 그러면 dp[100][20]은 dp[100][10+A의 무게] 로써 나머지 10을 채운 행복 +A의 행복 값을 담고 있습니다. 그런데 현재 dp[100][10]을 dp[100][20]보다 먼저 계산해서 대입해 넣기 때문에, 실상 dp[100][10]은 A를 넣은 행복 값도 담고 있습니다.

jminji98   3년 전

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)를 가져와야 할 것같아요 

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