Revisions to Knapsack problem - recursive approach with memoization

Question Protected by Mast♦

occurred May 28, 2023 at 10:27

edited tags

Link

edited Aug 6, 2021 at 9:29

Toby Speight

88.7k
14
104
327

Rollback to Revision 3

Source Link

edited Dec 24, 2018 at 8:01

Mast ♦

13.9k
12
57
128

'''Programming Assignment #4: Question 1'''
def knapsackknapSack(max_weightW , weightswt , valuesval , max_valuen):
    '''Recursive method for the knapsack problem 
 (with memoization)'''
    # Base Case 
    if max_valuen == 0 or max_weightW == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if weights[max_value(wt[n-1] > max_weightW): 
        return knapsackknapSack(max_weightW , weightswt , valuesval , max_valuen-1) 
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] (lookup[n][W]!= -1):
        return LOOKUP[max_value][max_weight]lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 +=else: VALUES[max_value-1]
    # val1 stores the maximumx possible= profitmax(val[n-1] when+ theknapSack(W-wt[n-1] last, itemwt is, included
val , n-1), knapSack(W val2, =wt knapsack(max_weight, weights,val values, max_valuen-1))
    # val2 stores the maximum possible profit when the last item is excluded
    templookup[n][W] = max(val1, val2)x
    LOOKUP[max_value][max_weight] = temp
  return x
 return temp
#End of function knapsackknapSack 
  
#To test above function 
VALUESval = []
WEIGHTSwt = []
#Reading the data file
with open("knapsack.txt") as f:
    FIRST_LINEfirst_line = f.readline().split()
    MAX_WEIGHTW = int(FIRST_LINE[0]first_line[0])
    MAX_VALUEn = int(FIRST_LINE[1]first_line[1])
    for line in f:
        words = line.split()
        VALUESval.append(int(words[0]))
        WEIGHTSwt.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUPlookup = [[-1 for i in range(MAX_WEIGHT+1W+1)] for j in range(MAX_VALUE+1n+1)]
#Function knapsack is invoked
print knapsackknapSack(MAX_WEIGHTW, WEIGHTSwt, VALUESval, MAX_VALUEn)

'''Programming Assignment #4: Question 2'''
def knapsackknapSack(max_weightW , weightswt , valuesval , max_valuen):
    '''Recursive method for the knapsack problem 
 (with memoization)'''
    # Base Case 
    if max_valuen == 0 or max_weightW == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if weights[max_value(wt[n-1] > max_weightW): 
        return knapsackknapSack(max_weightW , weightswt , valuesval , max_valuen-1) 
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] (lookup[n][W]!= -1):
        return LOOKUP[max_value][max_weight]lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 +=else: VALUES[max_value-1]
    # val1 stores the maximumx possible= profitmax(val[n-1] when+ theknapSack(W-wt[n-1] last, itemwt is, included
val , n-1), knapSack(W val2, =wt knapsack(max_weight, weights,val values, max_valuen-1))
    # val2 stores the maximum possible profit when the last item is excluded
    templookup[n][W] = max(val1, val2)x
    LOOKUP[max_value][max_weight] = temp
  return x
 return temp
#End of function knapsackknapSack 
  
#To test above function 
VALUESval = []
WEIGHTSwt = []
#Reading the data file
with open("knapsack_big.txt") as f:
    FIRST_LINEfirst_line = f.readline().split()
    MAX_WEIGHTW = int(FIRST_LINE[0]first_line[0])
    MAX_VALUEn = int(FIRST_LINE[1]first_line[1])
    for line in f:
        words = line.split()
        VALUESval.append(int(words[0]))
        WEIGHTSwt.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUPlookup = [[-1 for i in range(MAX_WEIGHT+1W+1)] for j in range(MAX_VALUE+1n+1)]
#Function knapsack is invoked
print knapsackknapSack(MAX_WEIGHTW, WEIGHTSwt, VALUESval, MAX_VALUEn)

'''Programming Assignment #4: Question 1'''
def knapsack(max_weight, weights, values, max_value):
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case
    if max_value == 0 or max_weight == 0:
        return 0
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if weights[max_value-1] > max_weight:
        return knapsack(max_weight, weights, values, max_value-1)
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] != -1:
        return LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 += VALUES[max_value-1]
    # val1 stores the maximum possible profit when the last item is included
    val2 = knapsack(max_weight, weights, values, max_value-1)
    # val2 stores the maximum possible profit when the last item is excluded
    temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
    return temp
#End of function knapsack
#To test above function
VALUES = []
WEIGHTS = []
#Reading the data file
with open("knapsack.txt") as f:
    FIRST_LINE = f.readline().split()
    MAX_WEIGHT = int(FIRST_LINE[0])
    MAX_VALUE = int(FIRST_LINE[1])
    for line in f:
        words = line.split()
        VALUES.append(int(words[0]))
        WEIGHTS.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(MAX_WEIGHT+1)] for j in range(MAX_VALUE+1)]
#Function knapsack is invoked
print knapsack(MAX_WEIGHT, WEIGHTS, VALUES, MAX_VALUE)

'''Programming Assignment #4: Question 2'''
def knapsack(max_weight, weights, values, max_value):
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case
    if max_value == 0 or max_weight == 0:
        return 0
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if weights[max_value-1] > max_weight:
        return knapsack(max_weight, weights, values, max_value-1)
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] != -1:
        return LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 += VALUES[max_value-1]
    # val1 stores the maximum possible profit when the last item is included
    val2 = knapsack(max_weight, weights, values, max_value-1)
    # val2 stores the maximum possible profit when the last item is excluded
    temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
    return temp
#End of function knapsack
#To test above function
VALUES = []
WEIGHTS = []
#Reading the data file
with open("knapsack_big.txt") as f:
    FIRST_LINE = f.readline().split()
    MAX_WEIGHT = int(FIRST_LINE[0])
    MAX_VALUE = int(FIRST_LINE[1])
    for line in f:
        words = line.split()
        VALUES.append(int(words[0]))
        WEIGHTS.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(MAX_WEIGHT+1)] for j in range(MAX_VALUE+1)]
#Function knapsack is invoked
print knapsack(MAX_WEIGHT, WEIGHTS, VALUES, MAX_VALUE)

def knapSack(W , wt , val , n):  
  
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]!=-1):
        return lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))
        lookup[n][W] = x
        return x
  
#End of function knapSack 
  
#To test above function 
val = []
wt = []
with open("knapsack.txt") as f:
    first_line = f.readline().split()
    W = int(first_line[0])
    n = int(first_line[1])
    for line in f:
      words = line.split()
      val.append(int(words[0]))
      wt.append(int(words[1])) 
lookup = [[-1 for i in range(W+1)] for j in range(n+1)]
print knapSack(W, wt, val, n)

def knapSack(W , wt , val , n):  
  
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]!=-1):
        return lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
        x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))
        lookup[n][W] = x
        return x
  
#End of function knapSack 
  
#To test above function 
val = []
wt = []
with open("knapsack_big.txt") as f:
    first_line = f.readline().split()
    W = int(first_line[0])
    n = int(first_line[1])
    for line in f:
      words = line.split()
      val.append(int(words[0]))
      wt.append(int(words[1])) 
lookup = [[-1 for i in range(W+1)] for j in range(n+1)]
print knapSack(W, wt, val, n)

Modified the code after running it through Pylint (score - 10/10), as suggested in an existing answer.

Source Link

edited Dec 24, 2018 at 7:57

user188780

def'''Programming knapSack(WAssignment ,#4: wtQuestion 1'''
def knapsack(max_weight, valweights, values, nmax_value): 
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case 
    if nmax_value == 0 or Wmax_weight == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[nweights[max_value-1] > W)max_weight: 
        return knapSackknapsack(W max_weight, wt weights, val values, nmax_value-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]LOOKUP[max_value][max_weight] != -1):
        return lookup[n][W]     LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else:val1 
 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    xval1 =+= max(val[nVALUES[max_value-1] 
 + knapSack(W-wt[n-1] , wt# ,val1 valstores ,the n-1),maximum knapSack(Wpossible ,profit wtwhen the last item is included
    val2 = knapsack(max_weight, valweights, values, nmax_value-1))
    # val2 stores the lookup[n][W]maximum =possible x
profit when the last item is excluded
  return x temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
#End of function knapSack return temp
#End of function knapsack
#To test above function 
valVALUES = []
wtWEIGHTS = []
#Reading the data file
with open("knapsack.txt") as f:
    first_lineFIRST_LINE = f.readline().split()
    WMAX_WEIGHT = int(first_line[0]FIRST_LINE[0])
    nMAX_VALUE = int(first_line[1]FIRST_LINE[1])
    for line in f:
        words = line.split()
      val  VALUES.append(int(words[0]))
      wt  WEIGHTS.append(int(words[1])) 
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(W+1MAX_WEIGHT+1)] for j in range(n+1MAX_VALUE+1)]
#Function knapsack is invoked
print knapSackknapsack(WMAX_WEIGHT, wtWEIGHTS, valVALUES, nMAX_VALUE)

def'''Programming knapSack(WAssignment ,#4: wtQuestion 2'''
def knapsack(max_weight, valweights, values, nmax_value): 
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case 
    if nmax_value == 0 or Wmax_weight == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[nweights[max_value-1] > W)max_weight: 
        return knapSackknapsack(W max_weight, wt weights, val values, nmax_value-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]LOOKUP[max_value][max_weight] != -1):
        return lookup[n][W]     LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else:val1 
 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    xval1 =+= max(val[nVALUES[max_value-1] 
 + knapSack(W-wt[n-1] , wt# ,val1 valstores ,the n-1),maximum knapSack(Wpossible ,profit wtwhen the last item is included
    val2 = knapsack(max_weight, valweights, values, nmax_value-1))
    # val2 stores the lookup[n][W]maximum =possible x
profit when the last item is excluded
  return x temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
#End of function knapSack return temp
#End of function knapsack
#To test above function 
valVALUES = []
wtWEIGHTS = []
#Reading the data file
with open("knapsack_big.txt") as f:
    first_lineFIRST_LINE = f.readline().split()
    WMAX_WEIGHT = int(first_line[0]FIRST_LINE[0])
    nMAX_VALUE = int(first_line[1]FIRST_LINE[1])
    for line in f:
        words = line.split()
      val  VALUES.append(int(words[0]))
      wt  WEIGHTS.append(int(words[1])) 
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(W+1MAX_WEIGHT+1)] for j in range(n+1MAX_VALUE+1)]
#Function knapsack is invoked
print knapSackknapsack(WMAX_WEIGHT, wtWEIGHTS, valVALUES, nMAX_VALUE)

def knapSack(W , wt , val , n): 
  
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]!=-1):
        return lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
         x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))
        lookup[n][W] = x
        return x
  
#End of function knapSack 
  
#To test above function 
val = []
wt = []
with open("knapsack.txt") as f:
    first_line = f.readline().split()
    W = int(first_line[0])
    n = int(first_line[1])
    for line in f:
      words = line.split()
      val.append(int(words[0]))
      wt.append(int(words[1])) 
lookup = [[-1 for i in range(W+1)] for j in range(n+1)]
print knapSack(W, wt, val, n)

def knapSack(W , wt , val , n): 
  
    # Base Case 
    if n == 0 or W == 0 : 
        return 0
    # If weight of the nth item is more than Knapsack of capacity 
    # W, then this item cannot be included in the optimal solution 
    if (wt[n-1] > W): 
        return knapSack(W , wt , val , n-1) 
    # Check for required value in lookup table first
    if (lookup[n][W]!=-1):
        return lookup[n][W]     
    # Add to lookup table and return the maximum of two cases: 
    # (1) nth item included 
    # (2) not included 
    else: 
         x = max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1), knapSack(W , wt , val , n-1))
        lookup[n][W] = x
        return x
  
#End of function knapSack 
  
#To test above function 
val = []
wt = []
with open("knapsack_big.txt") as f:
    first_line = f.readline().split()
    W = int(first_line[0])
    n = int(first_line[1])
    for line in f:
      words = line.split()
      val.append(int(words[0]))
      wt.append(int(words[1])) 
lookup = [[-1 for i in range(W+1)] for j in range(n+1)]
print knapSack(W, wt, val, n)

'''Programming Assignment #4: Question 1'''
def knapsack(max_weight, weights, values, max_value):
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case
    if max_value == 0 or max_weight == 0:
        return 0
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if weights[max_value-1] > max_weight:
        return knapsack(max_weight, weights, values, max_value-1)
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] != -1:
        return LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 += VALUES[max_value-1] 
    # val1 stores the maximum possible profit when the last item is included
    val2 = knapsack(max_weight, weights, values, max_value-1)
    # val2 stores the maximum possible profit when the last item is excluded
    temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
    return temp
#End of function knapsack
#To test above function
VALUES = []
WEIGHTS = []
#Reading the data file
with open("knapsack.txt") as f:
    FIRST_LINE = f.readline().split()
    MAX_WEIGHT = int(FIRST_LINE[0])
    MAX_VALUE = int(FIRST_LINE[1])
    for line in f:
        words = line.split()
        VALUES.append(int(words[0]))
        WEIGHTS.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(MAX_WEIGHT+1)] for j in range(MAX_VALUE+1)]
#Function knapsack is invoked
print knapsack(MAX_WEIGHT, WEIGHTS, VALUES, MAX_VALUE)

'''Programming Assignment #4: Question 2'''
def knapsack(max_weight, weights, values, max_value):
    '''Recursive method for the knapsack problem (with memoization)'''
    # Base Case
    if max_value == 0 or max_weight == 0:
        return 0
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if weights[max_value-1] > max_weight:
        return knapsack(max_weight, weights, values, max_value-1)
    # Check for required value in lookup table first
    if LOOKUP[max_value][max_weight] != -1:
        return LOOKUP[max_value][max_weight]
    # Add to lookup table and return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    val1 = knapsack(max_weight-WEIGHTS[max_value-1], weights, values, max_value-1)
    val1 += VALUES[max_value-1] 
    # val1 stores the maximum possible profit when the last item is included
    val2 = knapsack(max_weight, weights, values, max_value-1)
    # val2 stores the maximum possible profit when the last item is excluded
    temp = max(val1, val2)
    LOOKUP[max_value][max_weight] = temp
    return temp
#End of function knapsack
#To test above function
VALUES = []
WEIGHTS = []
#Reading the data file
with open("knapsack_big.txt") as f:
    FIRST_LINE = f.readline().split()
    MAX_WEIGHT = int(FIRST_LINE[0])
    MAX_VALUE = int(FIRST_LINE[1])
    for line in f:
        words = line.split()
        VALUES.append(int(words[0]))
        WEIGHTS.append(int(words[1]))
#Declaring and initializing the lookup table
LOOKUP = [[-1 for i in range(MAX_WEIGHT+1)] for j in range(MAX_VALUE+1)]
#Function knapsack is invoked
print knapsack(MAX_WEIGHT, WEIGHTS, VALUES, MAX_VALUE)

Tweeted twitter.com/StackCodeReview/status/1077081577824366592

occurred Dec 24, 2018 at 6:00

edited tags

Link

edited Dec 23, 2018 at 21:23

user188780

Loading

added 52 characters in body

Source Link

edited Dec 23, 2018 at 21:17

user188780

Loading

Source Link

asked Dec 23, 2018 at 21:11

user188780

Loading

Stack Exchange Network

Return to Question