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
