qls0860   5년 전

도대체 어떤 점화식을 짜야 시간 초과가 안날까요...

배열 다 그리면서 점화식 짜봤는데 시간 초과가 나요

너무 어렵습니다 ㅠㅠ

jh05013   5년 전

이 문제처럼 "x번째 물건을 K_x개까지 가져갈 수 있다"는 조건이 붙는 배낭 문제는 x번째 물건을 K_x개 복사한 뒤 "모든 물건은 하나씩만 가져갈 수 있다"는 조건이 붙는 배낭 문제로 바꿀 수 있고, 이것이 질문에 올리신 풀이와 비슷합니다. 문제는 이렇게 하면 물건이 너무 많아진다는 것입니다.

예를 들어, K=3인 물건 X가 있어서 이것을 3개 복사했다고 해 봅시다. 각각의 복사에 A, B, C라고 이름붙이면, A, B를 가져가는 거나, B, C를 가져가는 거나, A, C를 가져가는 거나 아무 차이가 없습니다. 셋 다 "물건 X를 두 개 가져간다"와 동일한 의미를 갖는 것입니다. 그런데 이렇게 복사해 놓고 DP를 하면 세 경우 모두를 고려하고 똑같은 DP값을 여러번 계산하게 됩니다. 물건 X을 가져가는 경우의 수는 원래 0부터 3까지 총 4가지였는데, 이렇게 복사하면 23=8가지가 되므로 상당량의 중복이 생깁니다.

하나 발상의 전환을 하면 물건을 3개보다 적게 만들고도 물건 X를 가져가는 4가지 경우의 수를 모두 표현할 수 있습니다.

qls0860   5년 전

일단 답글 감사합니다

저 점화식에서 

' dp[i-1][j-(w[i-1]*k)] '  <<< 이 부분 있잖아요.

j-(w[i-1])*k 의 무게만큼 안샀을 때 가치는 k의 값마다 다 다르잖아요.

예를 들어 p[i-1]을 1개 사면 배낭에서 그 무게만큼 뺐을 때의 가치, 2개 사면 2개 뺏을 때의 가치... 

그게 각각 다 다르니까 다 비교해줘야 되는 거 아니에요?

jh05013   5년 전

다 비교하면 시간초과가 날 수밖에 없고, 꼭 다 비교해야 답을 낼 수 있는 것도 아닙니다. 예를 들어 dp[i-1][j] + p[i]가 dp[i-1][j+w[i]]보다 작으면, x가 얼마가 되더라도 무게 j가 들어간 배낭에 i번째 물건을 x개 넣는 것보다 무게 j+w[i]가 들어간 배낭에 x-1개 넣는 것이 항상 이득입니다. 이런 식으로 비교 횟수를 적절히 끊어서 푸는 방법도 있습니다.

qls0860   5년 전

dp[i-1][j] + p[i] < dp[i-1][j+w[i]]  일 때

dp[i][j+w[i]] = max(dp[i-1][j], p[i]*(x-1)) 이라는 건가요?

jh05013   5년 전

그건 전혀 아니고, 모든 경우를 비교할 필요가 없다는 것이 요점입니다.

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