wish_me's blog

Help in Arpa's weak amphitheater and Mehrdad's valuable Hoses
By wish_me, history, 7 years ago, In English

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

http://mirror.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 ?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply