CODEWITHSUNDEEP
pythonknapsack-problem
user4805479
user4805479

Reputation:

Unbounded Knapsack in Python

Consider the following problem statement:

Given a list of n integers, w={w1,w2,…,wn}, and another integer, W representing the expected sum. Select zero or more numbers from 'w' such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (W).

see code: 

def KnapSack (i, w, X, W):
    if ( w[i:] == [] and X >= 0):
        return  ( W - X )   
    elif ( X < 0 ):
        return 0        
    else:       
        return max (KnapSack(i+1, w, X, W), KnapSack(i+1, w, X-w[i], W))

n, W = raw_input().split()
n, W = [int(n), int(W)]
w = map(int, raw_input().split())
print KnapSack (0, w[0:], W, W)

n and W, represent the length of list w and expected sum, respectively. Second line consists of n space separated integers, w1,w2,…,wn, representing the elements of list w.

I'm really having trouble with the unbounded condition that permits multiple selections from 'w'. Please help!

Upvotes: 1

Views: 2291

Answers (1)

Luka Rahne
Luka Rahne

Reputation: 10447

If each element can be selected multiple times, this is no longer knapsack-problem (that is NP hard), and can apply Bézout's identity that can be solved applying extended euclidean algorithm.

or you can just fix to somthing like

return max (KnapSack(i+1, w, X, W), KnapSack(i, w, X-w[i], W))

Upvotes: 3

Related Questions