python (12.9k questions)

javascript (9.2k questions)

reactjs (4.7k questions)

java (4.2k questions)

java (4.2k questions)

c# (3.5k questions)

c# (3.5k questions)

html (3.3k questions)

Questions - subset-sum

Subset sum variation, dynamic programming

I'm trying to do the classic subset sum problem with the caveat that the sum of the subset should get as close as possible to tgt without exceeding it. Here is my recurrence which finds how far away t...
test-img

BCBugajski

python

dynamic-programming

subset-sum

Votes: 0

Answers: 1

Latest Answer

I do not think you have to completely change the whole function. The table is used to store calculations that could be used again later. You can add the result of each recursive call to your dict. If ...
test-img

JANO

Count the sum of subsets of size k when the sum is (Greater than or equal to R) or (Lesser than or equal to L)

def knapSack(A,L,R,K,N,Sum): if(K==0): if((L>=Sum)or(R<=Sum)): return 1 else: return 0 if((N==0)and(K!=0)): return 0 else: ret...
test-img

Arun kumar

count

dynamic-programming

subset-sum

bottom-up

Votes: 0

Answers: 1

Latest Answer

Here is a dynamic programming algorithm you can use. The algorithm will be used to generate all subsets of size K. This algorithm uses one element of A one after another to build subsets. STEPS Initi...
test-img

Wilson

Subset sum decision problem -- how to verify &quot;false&quot; case in polynomial time?

I'm having a bit of trouble understanding how one would verify if there is no solution to a given instance of the subset sum problem in polynomial time. Of course you could easily verify the positive ...
test-img

user491880

complexity-theory

theory

subset-sum

Votes: 0

Answers: 1

Latest Answer

It’s actually not known how to do this - and indeed it’s conjectured that it’s not possible to do so! The class NP consists of problems where “yes” instances can be verified in polynomial time. The su...
test-img

templatetypedef

Posts

Questions

Blogs

Jobs