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.
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!
Small challenge: Does anyone know how to do it by updating the states by checking for
i - wj >= 0
instead ofi + wj <= w
? I tried to do it but it was a bit hard so I gave up and did this instead.Try swapping dimensions in the original code. I believe it might increase performance of the code
Your suggestion was due to caching for the multidimensional array right?
https://atcoder.jp/contests/dp/submissions/41293376
This still gives TLE, I guess multidimensional array access is way too slow
Why do I have a feeling that you love watching chess content?
lol its true
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