Technical Interview Practice: Python - Knapsack With Memoization: Filling in the Grid

In the section Technical Interview Practice: Python - Knapsack With Memoization: Filling in the Grid: Python I don’t understand why in line 6 it is necessary to increment the row number. Doesn’t the loop already cause the iteration over the different row numbers that are defined by the enumeration?

from util import Loot

def knapsack(loot, weight_limit):
  grid = [[0 for col in range(weight_limit + 1)] for row in range(len(loot) + 1)]
  for row, item in enumerate(loot):
    **row = row + 1**
    for col in range(weight_limit + 1):
      weight_capacity = col
      # 1.
      if item.weight <= weight_capacity:
        item_weight = item.weight 
        item_value = item.value
        # 2.
        previous_best_less_item_weight = grid[row - 1][weight_capacity - item_weight]
        capacity_value_with_item = item_value + previous_best_less_item_weight
        # 3.
        capacity_value_without_item = grid[row - 1][col]
        grid[row][col] = max(capacity_value_with_item, capacity_value_without_item)
      else:
        grid[row][col] = grid[row - 1][col]
  # 5.
  return grid[-1][-1]
    
available_loot = [Loot("Clock", 3, 8), Loot("Vase", 4, 12), Loot("Diamond", 1, 7)]
weight_capacity = 4
best_combo = knapsack(available_loot, weight_capacity)
print("The ideal loot given capacity {0} is\n{1}".format(weight_capacity, best_combo))

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.