Maximum Value of the Loot

Problem Introduction:

A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag. Problem Description

Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format: The first line of the input contains the number 𝑛 of items and the capacity 𝑊 of a knapsack. The next 𝑛 lines define the values and weights of the items. The 𝑖-th line contains integers 𝑣𝑖 and 𝑤𝑖—the value and the weight of 𝑖-th item, respectively.
Constraints: 1≤𝑛≤103,0≤𝑊 ≤2·106;0≤𝑣𝑖 ≤2·106,0<𝑤𝑖 ≤2·106 for all 1≤𝑖≤𝑛.All the numbers are integers.
Output Format Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most −3 your answer, while being computed correctly, can turn out to be wrong because of rounding issues).

Sample 1.

Input:
3 50
60 20
100 50
120 30

Output:
180.0000
To achieve the value 180, we take the first item and the third item into the bag.

Sample 2.

Input:
1 10
500 30
Output:
166.6667

My code:

# Maximum Value of the Lootdef knapsack(n, capacity, value_list, weight_list):unitValues_list = []#First lets calculate the unitValues_listfor i in range (n):unitValue = (value_list[i]/weight_list[i])unitValues_list.append(unitValue)#Now lets fill the knapsack, intake is how much is in the bag at the moment!intake = 0max_value = 0factor = Truewhile(factor):max_index = unitValues_list.index(max(unitValues_list, default=0)) # this gives the index of the max valued elementif(weight_list[max_index] <= capacity):# In this case, full item is taken inintake = weight_list[max_index]capacity -= weight_list[max_index]max_value += value_list[max_index]else:# weight_list[max_index] > capacity# In this case, fraction to be takenintake += capacitycapacity = 0max_value += unitValues_list[max_index]*intakeweight_list.pop(max_index)value_list.pop(max_index)unitValues_list.pop(max_index)print(weight_list)n -= 1 #no. of items leftfactor = ((n != 0) if ((capacity != 0) if True else False) else False)return max_valueif __name__ == "__main__":value_list = []weight_list = []#The first line of the input contains the number 𝑛 of items and the capacity 𝑊 of a knapsack. #The next 𝑛 lines define the values and weights of the items. n , capacity = map(int, input().split())for i in range (n):value , weight = map(int, input().split())value_list.append(value)weight_list.append(weight)#Output the maximal value of fractions of items that fit into the knapsack.print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))

I keep getting an error:

Failed case #6/13: Wrong answer
got: 8740.3008948546 expected: 7777.731
(Time used: 0.00/5.00, memory used: 9191424/671088640.)

Correcting Wrong Answer

Corrected fraction to be taken by changing

intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake

To

fraction = capacity / weight_list[max_index] 
max_value += value_list[max_index]*fraction
capacity = 0 

Refactored Code

def knapsack(n, capacity, value_list, weight_list):unitValues_list = []#First lets calculate the unitValues_listfor i in range (n):unitValue = (value_list[i]/weight_list[i])unitValues_list.append(unitValue)#Now lets fill the knapsack, intake is how much is in the bag at the moment!intake = 0max_value = 0factor = Truewhile(factor):max_index = unitValues_list.index(max(unitValues_list, default=0)) # this gives the index of the max valued elementif(weight_list[max_index] <= capacity):# In this case, full item is taken inintake = weight_list[max_index]capacity -= weight_list[max_index]max_value += value_list[max_index]else:# weight_list[max_index] > capacity# In this case, fraction to be takenfraction = capacity / weight_list[max_index] max_value += value_list[max_index]*fractioncapacity = int(capacity - (weight_list[max_index] * fraction))weight_list.pop(max_index)value_list.pop(max_index)unitValues_list.pop(max_index)print(weight_list)n -= 1 #no. of items leftfactor = ((n != 0) if ((capacity != 0) if True else False) else False)return max_valueif __name__ == "__main__":value_list = []weight_list = []#The first line of the input contains the number 𝑛 of items and the capacity 𝑊 of a knapsack. #The next 𝑛 lines define the values and weights of the items. n , capacity = map(int, input('n, capacity: ').split())for i in range (n):value , weight = map(int, input('value, weight: ').split())value_list.append(value)weight_list.append(weight)#Output the maximal value of fractions of items that fit into the knapsack.print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))

Note

Time was not mentioned as an issue.

Complexity can be changed from current O(n^2) algorithm to O(n*log(n)) by sorting unitValues_list rather than computing max each time.