DP에 대한 개인의 이해-가방
7723 단어 dp
for(int i=0;i<n;i++)
for(int j=W;j>=w[i];j++)
dp[j]=max(dp[j],dp[j-W[i]]+v[i]); 두 번째 순환에 주의해라. 왜 뒤에서 앞으로 밀어내는지 나도 모르겠다. 어쩌면 dp 뒤의 값은 앞의 값이 유도되어 왔기 때문에 뒤에서 앞으로 유도해야 한다.01 가방의 2: W가 크고 v[i]가 비교적 작을 때를 해결한다.추이식: 이런 문제는 dp[i+1][j]를 선택 전 i종의 물품으로 이해하여 가치가 j의 최소 무게를 초과하지 않도록 하는 것이다.시간의 복잡도는 O(n*sum(vi)(0<=i<=n))로 추정된다. dp[0][0]=0, dp[0][j]=INF(최대치)(초기화).dp[i+1][j]=min(dp[i][j],dp[i][j - v[i]] + w[i]) (else); 이 답안은 주의해야 한다. dp[n][j]<=W의 최대치 j이다.(이것은 내가 당시에 생각하지 못했던) 코드는 다음과 같다.
for(int i=0;i<n;i++)
for(int j=0;j<=max_n*max_v;j++)
if(j<v[i]) dp[i+1][j]=dp[i][j];
else dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+W[i]);완전 가방: (Complete Pack) 개념: n개의 아이템이 있는데 무게는 w[i]이고 가치는 v[i]입니다. 이 아이템들은 여러 번 구할 수 있습니다. 이 아이템들 중에서 총 무게가 W를 초과하지 않는 아이템을 골라서 최대 가치를 구합니다.이전 문제에 비해 하나의 물품을 여러 번 선택할 수 있다. 그러면 각 물품을 몇 개 선택하는 것이 가장 좋은지 판단하고 개수 대신 k를 도입해야 한다.추이식: dp[i+1][j]는 전 i종의 물품을 선택하여 무게가 j의 최대 가치를 초과하지 않도록 하는 것을 나타낸다.순추: dp[0][j]=0(초기화);dp[i+1][j]={max(dp[i+1][j],max(dp[i][j-k*w[i]]]+k*v[i])(k>=0)} 이렇게 하면 이 말에 대한'이런 물건을 얼마나 많이 넣을 수 있는지, 얼마나 많이 넣을 수 있는지'에 대한 가장 좋은 해석이다.코드는 다음과 같습니다.
for(int i=0;i<n;i++)
for(int j=0;j<=W;j++)
for(int k=0;k*w[i]<=j;k++)
dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);다시 생각해 보면 코드가 삼중순환이고 시간 복잡도가 O(nW^2)인 것을 발견하면 복잡도를 더 절약할 수 있는 사상이 있나요?어떤 것://완전 가방, 유도 과정:
max { dp[i][j - k * w[i]] + k * v[i] | (0 <= k) }
=max(dp[i][j],max {dp[i] [j-k* w[i]] + k* v[i] | (1<=k)})//k의 수치 범위를 k>= 0으로 되돌리려면:
//령t=k-1,t>=0,k=t+1;
=max( dp[i][j], max { dp[i][j - (t + 1) * w[i]] + (t + 1) * v[i] | (0 <= t) } )
=max( dp[i][j], max { dp[i][(j - w[i]) - t * w[i]] + t * v[i] + v[i] | (0 <= t) } )
=max(dp[i][j],max {dp[i+1] [j-w[i]] + v[i]})//는 이전 i항에서 계산한 것을 i+1항으로 미루고 실질 t* w[i]는 이미 계산된 것으로 원서에 쓴 i+1이지만 잘 이해하지 못했으니 i와 i-1을 비교하는 것이 아니겠지//혹시 i항에서 유도된 것이라면 i+1항과 비교해야 한다.정말 잘 모르겠네요.이를 통해 알 수 있듯이 한 수는 작은 것에서 큰 것으로 다른 수의 k배(k>=0)를 빼고 사실은 이 수는 작은 것에서 큰 것으로 이 수를 빼는 것이다. 물론 이 답안은 점차적으로 미루어야 한다. 즉, 계산한 후에 이미 기록했고 나중에 다시 사용할 때 바로 이 이치이다.이렇게 시간의 복잡도는 01배낭과 같다. 그러면 추이식 최적화 후의 코드는 다음과 같다. (1차원 dp수조)
for(int i=0;i<n;i++)
for(int j=w[i];j<=W;j++)
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);생각해보니까 이게 왜 앞에서 뒤로 밀려?아마도 dp는 자신과 비교하고 여러 번 물건을 선택하는 개념이 존재하기 때문에 여러 번 선택하는 것도 수조에 기록될 것이다.다중 가방: 개념: n개 아이템이 있고, 무게는 w[i]이며, 가치는 v[i]이며, 각 아이템 a[i]개는 이 아이템 중에서 총 무게가 W를 초과하지 않는 아이템을 골라 최대 가치를 구한다.이 문제는 이전에 비해 비슷하지만 큰 차이가 있다. 비록 상기 문제의 첫 번째 방법으로 해결할 수 있지만 시간의 복잡도는 틀림없이 넘을 수 없기 때문에 기교가 생겼다.기교: a[i]를 1,2,4,8,16,......,2^(k-1), a[i]-2^(k-1)로 나눈다.이렇게 하면 무슨 효과가 있습니까?우선 우리가 이 수를 한 번에 매거해서 a[i]의 수를 모두 매거했는지 확인하자(이 점은 나도 납득하지 못했지만 내 이해는 그렇지만 우리가 뒤에서 다른 수를 매거할 때 우리는 dp의 값에 따라 모든 수를 매거하는 효과에 도달할 수 있다). 확정한 후에 시간의 복잡도가 낮아졌는지 O(nWa[i])에서 O(nWlog(a[i])로 낮아졌는지 확인한다.그래서 우리의 추이식은 완전 배낭의 첫 번째 상황과 같다.추이식: dp[i+1][j]는 전 i종의 물품을 선택하여 무게가 j의 최대 가치를 초과하지 않도록 하는 것을 나타낸다.순추: dp[0][j]=0(초기화);dp[i+1][j]={max(dp[i+1][j],max(dp[i][j-k*w[i]]]+k*v[i])(k>=0)} 이것도 이 말의'이런 물건을 몇 가지 형태로 넣을 수 있는지, 넣을 수 있는지'에 대한 가장 좋은 해석이다.그러면 코드는 다음과 같습니다.
for(int i=0;i<n;i++)
{
if(a[i]*w[i]<W)
complete(w[i],v[i],W);
else
{
int k=1;
while(k<a[i])
{
ZeroOne(k*w[i],k*v[i],W);
a[i]-=k;
k<<=1;
}
ZeroOne(a[i]*w[i],a[i]*v[i],W);
}
}OK!!!배낭 문제는 이것으로 끝내고, 나도 아직 무슨 문제를 연습한 적이 없어, 한창 준비하고 있어...그때 문제를 풀고 보충할 것이 있는지 없는지...take it easy ...
좋은 웹페이지 즐겨찾기
