Is there anyone who can help me improve the time complexity of this backpack algorithm, for which I already use sliding array to improve the space complexity.
The problem is as follows:
nitems with size
A[i], an integer
mdenotes the size of a backpack. How full you can fill this backpack?
If we have 4 items with size
[2, 3, 5, 7], and the backpack size is 11, we can select
[2, 3, 5], so that the max size for this backpack is 10. If the backpack size is 12, we can select
[2, 3, 7] and fill it completely.
The function should return the max size we can fill in the given backpack.
class Solution: # @param m: An integer m denotes the size of a backpack # @param A: Given n items with size A[i] # @return: The maximum size def backPack(self, m, A): # write your code here n = len(A) f = [[False for x in range(m+1)] for y in range(2)] for i in range(n+1): f[i%2] = True for i in range(1, n+1): for j in range(1, m+1): f[i%2][j] = f[(i-1)%2][j] if j >= A[i-1] and f[(i-1)%2][j-A[i-1]]: f[i%2][j] = True max = 0 for i in range(m+1): if f[n%2][i]: max = i return max