### wish_me's blog

By wish_me, history, 2 years ago, ,

Hey, Everyone I am unable to understand that how should I apply knapsack in this problem

http://codeforces.com/problemset/problem/741/B

Because it contains different groups.Thus Mine complexity is coming O(W*N*N).I saw the editorial but unable to understand the solution.Can anyone explain ?

• -3

 » 2 years ago, # | ← Rev. 5 →   0 Sorry if I misunderstood your problem regarding the solution,but I will try to explain it entirely. Firstly,imagine the relationships betweeb Hoses as a graph.2 hoses are in the same friendship group if they are in the same connected component.You can run a dfs/bfs to find all the connected components.Why does it matter?If two Hoses are n the same friendship group we can't take one without the other,so we imagine each group as a super-Hose with the weight that is the sum of the weights of the hoses of the group,and the beauty the sum of the beauties of the hoses in the group. Secondly,we have at most n items(there can't be more than n connected components) so we can just apply the classical knapsack in O(n*k):dp[ i ][ j ]=max(dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ]) where Sweight[ i ],Sbeauty[ i ] are the weight and the beauty of i-th super hose.You can optimize knapsack's memory by always holding only the current and the previous line or having just an array and going with the j index in reversed order (from w to 1) but I don't believe this is essential if you have enough memory.
•  » » 2 years ago, # ^ |   0 Thanks.I was not applying the idea of connected component.
•  » » 2 years ago, # ^ |   0 But I think you didn't cover the case suppose we have three groups (1,2,3),(4,5),(6,7) Now As we can take maximum 1 from each group or can take all elements of the group.Now suppose maximum beauty with weight constraint come from this arrangement (2,4,5,7 i.e 2 nd from 1st set ,all from 2nd set,7 from last set),I hope you understand.
•  » » » 2 years ago, # ^ |   0 Yeah,I'm sorry.I didn't solve the problem so I wasn't that careful at the statement.Each time you try to insert a super hose,you try to insert each hose that is from its group.So the recurrence becomes dp[ i ][ j ]=max((dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ]), max{dp[ i-1 ][j-weight[ x ] ]+beauty[ x ]}),where x is successively,each hose from i-th group.
 » 2 years ago, # |   0 Run a simple dfs/bfs to find all the connected components. For each connected component store its total weight and beauty and also all the vertices in it.Now there are 3 cases for each component, either take all of the vertices in it, take only 1 of the vertices in it or don't take anything at all. Now while going through connected components you can simply go through all its vertices and select the one which maximizes the answer.My submission: http://codeforces.com/contest/741/submission/33745764