Knapsack DP by looping through capacity first, feat. Python optimisation

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

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

import sys
 
input = sys.stdin.readline
 
 
def solve(n, w, arr):
    dp = [(0, []) for _ in range(w + 1)]
    dp[0] = (0, arr)
    ans = 0
    for i in range(w + 1):
        for wj, vj in dp[i][1]:
            if i + wj <= w and dp[i][0] + vj > dp[i + wj][0]:
                remaining = [x[:] for x in dp[i][1]]
                remaining.remove((wj, vj))
                dp[i + wj] = (dp[i][0] + vj, remaining)
        ans = max(ans, dp[i][0])
 
    print(ans)
 
 
def main():
    n, w = list(map(int, input().split()))
    arr = [tuple(map(int, input().split())) for _ in range(n)]
    solve(n, w, arr)
 
 
main()

https://atcoder.jp/contests/dp/submissions/41292224

Here is the optimised code that passes all testcases:

import sys
 
input = sys.stdin.readline
 
 
def solve(n, w, arr):
    dp1 = [0] * (w + 1)
    dp2 = [[] for _ in range(w + 1)]
    dp2[0] = arr
    ans = 0
    for i in range(w + 1):
        for wj, vj in dp2[i]:
            if i + wj <= w and dp1[i] + vj > dp1[i + wj]:
                dp1[i + wj] = dp1[i] + vj
                dp2[i + wj] = dp2[i][:]
                dp2[i + wj].remove((wj, vj))
        ans = max(ans, dp1[i])
 
    print(ans)
 
 
def main():
    n, w = list(map(int, input().split()))
    arr = [tuple(map(int, input().split())) for _ in range(n)]
    solve(n, w, arr)
 
 
main()

https://atcoder.jp/contests/dp/submissions/41292474

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!

Comments (6)

Write comment?

drugkeeper

18 months ago, # |

← Rev. 2 →

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.

→ Reply

lis05

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

18 months ago, # ^ |

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

theAyconic1

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

drugkeeper's blog