Oct-02-2020, 05:27 PM
import pandas as pd df = pd.read_csv('Instances.csv', header = 1) def Knapsack(K,s,v,n): # 3 & 4 x = [0] * n z = 0 # 5 R = [] for i in range(n): R.append((i,v[i]/s[i])) print(R) # 6 R.sort(reverse=True, key=lambda x:x[1]) print(R) # reorder original lists as stated in question new_s = [] new_v = [] for r in R: new_s.append(s[r[0]]) new_v.append(v[r[0]]) # 7 & 8 u = 0 i = 0 # 9+ while u <= K and i < n: if new_s[i] + u <= K: x[i] = 1 u = u + new_s[i] z = z + new_v[i] elif new_s[i] + u > K: x[i] = (K-u)/(new_s[i]) u = u + (new_s[i] * x[i]) z = z + (new_v[i] * x[i]) i = i + 1 return (x, z) # To test above function v = df['Value'] s = df['Size'] K = df['Knapsack Capacity'][0] n = len(v) print(Knapsack(K,s,v,n))
Output:[(0, 0.6896929824561403), (1, 0.4934409687184662), (2, 0.058635394456289985), (3, 1.3706070287539935), (4, 2.553846153846154), (5, 2.009259259259259), (6, 7.236363636363635), (7, 0.9710806697108066), (8, 0.7977412731006159), (9, 0.33176838810641623), (10, 0.6615168539325842), (11, 0.18432203389830507), (12, 3.1095890410958904), (13, 37.400000000000006), (14, 0.2038216560509554), (15, 1.2998137802607075), (16, 0.602125147579693), (17, 0.541371158392435), (18, 1.309667673716012), (19, 1.2723658051689861), (20, 1.791489361702128), (21, 0.7649164677804295), (22, 2.9087591240875916), (23, 4.951807228915663), (24, 1.4912836767036448)]
[(13, 37.400000000000006), (6, 7.236363636363635), (23, 4.951807228915663), (12, 3.1095890410958904), (22, 2.9087591240875916), (4, 2.553846153846154), (5, 2.009259259259259), (20, 1.791489361702128), (24, 1.4912836767036448), (3, 1.3706070287539935), (18, 1.309667673716012), (15, 1.2998137802607075), (19, 1.2723658051689861), (7, 0.9710806697108066), (8, 0.7977412731006159), (21, 0.7649164677804295), (0, 0.6896929824561403), (10, 0.6615168539325842), (16, 0.602125147579693), (17, 0.541371158392435), (1, 0.4934409687184662), (9, 0.33176838810641623), (14, 0.2038216560509554), (11, 0.18432203389830507), (2, 0.058635394456289985)]
([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.585215605749487, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], 8.546712525667353)
in the solution the [1,1,1... does not correspond to my original indexed items, it corresponds to the updated version so [1,1,1.. corresponds to 13,6,23. but i need the solution to show for the original