We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Solved it with BFS + memoization (cache). I start from top node of 0 then add all elements of arr, and keep doing that at every level of the tree until I hit K. If I don't hit K I return the largest sum I found.
Here is my solution, ignore the first attempt that tries to use dynamic programming(I already commented it out so you dont get confused). The second one with BFS and a queue is the good solution.
#!/bin/python3importmathimportosimportrandomimportreimportsys## Complete the 'unboundedKnapsack' function below.## The function is expected to return an INTEGER.# The function accepts following parameters:# 1. INTEGER k# 2. INTEGER_ARRAY arr## failed attempt to do dp# def unboundedKnapsack(k, arr):# arr = list(set(arr))# arr.sort()# smallest = arr[0]# if smallest > k or len(arr)==0:# return 0# # init cache# top_row = [0]*(1+k)# current_row = [0]*(1+k)# a = [] # partial arr# best_sum = 0# for n in arr:# if k % n == 0: # trivial case# # print(f'found with trivial case. k={k} n={n}')# return k# if n > k:# return best_sum# a.append(n)# # partially add up to k, col is current k in column# for col in range(smallest, k+1): # if col == 0:# current_row[col] = 0# continue# rem = col % n# if rem == 0:# current_row[col] = col # current best sum# continue# if n > col:# current_row[col] = top_row[col] # copy above value# break # exit this loop and continue to next n in arr# # check if adding current n with previous n can give us a better sum ie 3+4 = 7 when col is 7# current_best_sum = col - rem# for older_n in a:# sum_n = n + older_n# if sum_n > col:# break# rem2 = col % sum_n# if rem2 == 0:# current_best_sum = col # current best sum# break# # I want smallest remainder# if rem > rem2:# current_best_sum = col-rem2# print('after checking arr sums best sum is ', current_best_sum)# #check if the last sum plus any of n is better sum# # example a = [3,5] last best sum is 10 and col=13# previous = current_row[col-1] # for older_n in a:# s = previous + older_n# if s > col:# break# rem2 = col%s# if rem2 == 0:# current_best_sum = col# break# if s > current_best_sum:# current_best_sum = s# print('after checking Previous best sum is ', current_best_sum)# current_row[col] = current_best_sum# print('current arr',a)# print('top row: ', top_row)# print('current row: ', current_row)# top_row = current_row[:]# return current_row[-1]# final solution implementing a bfsdefunboundedKnapsack(k,arr):arr=list(set(arr))arr.sort()smallest=arr[0]ifsmallest>korlen(arr)==0:return0# init cachecache=[0]*(1+k)best_sum=0queue=[0]defis_multiple_of_arr(number):#checksifnumberisdivisiblebyanyofthearrnumbersforninarr:ifnumber>=nandnumber%n==0:returnTruereturnFalseifis_multiple_of_arr(k):returnk#trivialcasewhilelen(queue)>0:current=queue.pop(0)print('popedthisfromthequeue:',current)ifcache[current]==1:continuecache[current]=1forninarr:mysum=current+nprint(f'currentis:{current},nis{n}somysum={mysum}')# if is_multiple_of_arr(mysum):# return kifmysum==k:returnkifmysum<k:queue.append(mysum)print('pushedthistostack:',mysum)ifmysum>best_sum:best_sum=mysumreturnbest_sumif__name__=='__main__':fptr=open(os.environ['OUTPUT_PATH'],'w')t=int(input().strip())foriinrange(t):first_multiple_input=input().rstrip().split()n=int(first_multiple_input[0])k=int(first_multiple_input[1])arr=list(map(int,input().rstrip().split()))print('arris',arr)print('kis',k)result=unboundedKnapsack(k,arr)fptr.write(str(result)+'\n')fptr.close()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Knapsack
You are viewing a single comment's thread. Return to all comments →
Solved it with BFS + memoization (cache). I start from top node of 0 then add all elements of arr, and keep doing that at every level of the tree until I hit K. If I don't hit K I return the largest sum I found.
Here is my solution, ignore the first attempt that tries to use dynamic programming(I already commented it out so you dont get confused). The second one with BFS and a queue is the good solution.