Question

The Knapsack Problem in Python
Not using the exhaustive search method or the Dynamic Programming Method, find another method that accomplishes the task of the knapsack problem in python.

PLEASE DON'T USE THE EXHAUSTIVE SEARCH METHOD OR THE DYNAMIC PROGRAMMING METHOD, I DON'T NEED THOSE. THANK YOU.

Answer 1

Answer:

# A recursive implementation of 0-1 Knapsack Problem
# Returns the maximum value that can be put in a knapsack of capacity W
def knapSack(C, weight, val, n):
    # Base Case
    if n == 0 or C == 0:
        return 0

    # If weight of the nth item is more than Knapsack of capacity C,
    # then this item cannot be included in the solution
    if (weight[n - 1] > C):
        return knapSack(C, weight, val, n - 1)

    # return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    else:
        return max(val[n - 1] + knapSack(C - weight[n - 1], weight, val, n - 1),
                   knapSack(C, weight, val, n - 1))




# To test above function
val = [60, 100, 120]
weight = [10, 20, 30]
C = 50
n = len(val)
print(knapSack(C, weight, val, n))

Output:

C:\Userslasus\PycharmProjects\SamplelvenviScri 220 Process finished with exit code 0