drugkeeper's blog

By drugkeeper, history, 18 months ago, In English

I was doing AtCoder Educational DP Contest, Knapsack 1: https://atcoder.jp/contests/dp/tasks/dp_d

I wanted to loop through capacity instead of looping through each item in the array. All existing solutions that I have found had always looped through each item as the outermost loop. But what if I want to loop through each capacity as the outermost loop? (It is kind of impractical and I tunnel-visioned, but I digress).

Here is the solution I came up with:

My dp is two dimensional, with the first item of dp[i] being the max value, and the second item storing all the remaining items that we have not used, as a list of tuples. For every capacity we get the remaining items for that capacity, and try to use them. Now we just need to update the states for dp[i + wj] if its larger. The remaining items for dp[i + wj] will just be remaining items of dp[i], with that item removed.

Here is the code, which TLEs at the 7th testcase
Here is the optimised code that passes all testcases:

The main change was to seperate the dp array into dp1 and dp2, so that we can avoid unnecessary multidimensional array access. I believe this can still be further optimised but this is good enough to pass all testcases.

Thanks for reading!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Small challenge: Does anyone know how to do it by updating the states by checking for i - wj >= 0 instead of i + wj <= w? I tried to do it but it was a bit hard so I gave up and did this instead.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try swapping dimensions in the original code. I believe it might increase performance of the code

»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why do I have a feeling that you love watching chess content?

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think my solution runs in O(N^2 W) time complexity.

For example W = N, then lets assign every item with weight = 1 and value = 1, 2, 3 ...

My code will copy the remaining items for each dp[i], n, n-1, n-2 ... times, giving n^2 time complexity in the inner loop, while the outer loop is W

But we can avoid this behaviour by sorting the values in reverse order for each weight, then my code should ideally run in O(N log N + NW) time complexity I hope? I'm not sure