educative.io

Error in selected items detection algorithm

Courses
,
#1

Step 2 and 6 should say something like:

  1. Subtract the weight of the item D (5) from the current capacity (7) to jump to the new capacity (2) on the same row.
  2. Subtract the weight of the item B (2) from the current capacity (2) to jump to the new capacity (0) on the same row.

Selection_464
Selection_464933×638 110 KB

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5008218180812800

#2

Hi @Andres_Parra,

In the lesson, we’re getting the selected items on the basis of profit… which is also correct and your solution is based on weight. That is also correct.
Thank you for the suggestion

#3

Hi @lfrah_Dar!
Thank you for your answer. I just rechecked the code and you are right, it uses the profit and the algorithm is showing exactly that.
But this is not optimal. You are looking sequentially column by column where the expected next profit is, whereas if you use the weight you can jump directly to that column. I assumed the code did this, which is why I thought the algorithm was wrong.
So, my suggestion is change this:

def print_selected_elements(dp, weights, profits, capacity):
  print("Selected weights are: ", end='')
  n = len(weights)
  totalProfit = dp[n-1][capacity]
  for i in range(n-1, 0, -1):
    if totalProfit != dp[i - 1][capacity]:
      print(str(weights[i]) + " ", end='')
      capacity -= weights[i]
      totalProfit -= profits[i]

  if totalProfit != 0:
    print(str(weights[0]) + " ", end='')
  print()

To this:

def print_selected_elements(dp, weights, profits, capacity):
  print("Selected weights are: ", end='')
  i = len(weights) -1
  j = capacity
  totalProfit = dp[i][j]
  while totalProfit > 0:
    if i == 0 or totalProfit != dp[i-1][j]:
      print(str(weights[i]) + " ", end='')
      j -= weights[i]
      totalProfit -= profits[i]
    i -= 1
  print()