CODEWITHSUNDEEP
pythonalgorithmrecursionknapsack-problem
gbi1977
gbi1977

Reputation: 233

Naive Python recursive algorithm for unbounded Knapsack - achieve exact capacity

I'm trying to solve a knapsack problem using only recursion. The capacity is some positive integer and I also have a list of values/benefits, that each of its indexes corresponds to a successive portion of the capacity. Meaning the weight i has the value val[i-1].

I can (and should) repeat an item of some weight.

Also, I must fill the capacity entirely.

based on what I found here and in other sites, this is the code I wrote:

def knapsack(val, cap):
    n = len(val)
    return ks_exec(value, n, cap)


def ks_exec(val, i, cap):
    if cap==0 or i==0: 
        return 0
    if cap==1:
        return val[0]
    if i>cap:
        return ks_exec(val, i-1, cap)
    else:
        max(ks_exec(val[:-1],i-1,cap), \
            val[-1]+ks_exec(val,i-1,cap-i))

but it doesn't work.

Can anyone point me to where it fails?

Upvotes: 0

Views: 1060

Answers (1)

gbi1977
gbi1977

Reputation: 233

I think I got it!

The key is to refer to the case where the index/weight (which also denotes the length of the values list) is larger than the desired capacity - just reduce the function to it's original form (where the weight is equal to the capacity, and the list of values is as big).

def knapsack(val, cap):
n = len(val)
return ks_exec(value, n, cap)


def ks_exec(val, i, cap):
    if cap==0 or i==0: 
        return 0
    if cap==1:
        return val[0]
    if i>cap:
        return ks_exec(val[:cap], cap, cap)
        ''' we have redundent values for partitions larger than the 
            capacity, so we must reduce to the original problem with the 
            current given capacity.
        '''
    else:
        return max(ks_exec(val[:-1],i-1,cap), \
                   val[-1]+ks_exec(val,i,cap-i))

Upvotes: 0

Related Questions