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	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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!

	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