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

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

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!

	Rev.	Lang.	By	When	Δ	Comment
	en1		drugkeeper	2023-05-10 18:14:34	2835	Initial revision (published)

Rev.

Lang.

When

Comment

en1

drugkeeper

2023-05-10 18:14:34

2835

Initial revision (published)

History