Codepy - Python Online

import numpy as np
import time
import matplotlib.pyplot as plt

def fractional_knapsack(value, weight, capacity):
    
    index = list(range(len(value)))
    ratio = [v/w for v, w in zip(value, weight)]
    insertionSort(ratio,index)
    max_value = 0
    fractions = [0]*len(value)
    for i in index:
        if weight[i] <= capacity:
            fractions[i] = 1
            max_value += value[i]
            capacity -= weight[i]
        else:
            fractions[i] = capacity/weight[i]
            max_value += value[i]*capacity/weight[i]
            break
 
    return max_value, fractions

def insertionSort(a,index):
    for j in range(1,len(a)):
        key = a[j]
        key2 = index[j]
        i=j-1
        while i>=0 and key > a[i]:
            a[i+1] = a[i]
            index[i+1] = index[i]
            i-=1
        a[i+1] = key
        index[i+1] = key2
        
steps = 50
timeCount = np.zeros(steps)

for i in range(1,steps):
    number_of_items= 50*i
    value = np.random.randint(low=1, high=50000, size=number_of_items)
    weight = np.random.randint(low=1, high=50000, size=number_of_items)
    capacity=np.max(weight)
    start_time = time.process_time()
    print ("Loop is running for number of items:", number_of_items)
    max_value, fractions = fractional_knapsack(value, weight, capacity)
    timeCount[i] = time.process_time() -start_time

plt.plot(timeCount, label='Fractional Knapsack',)
plt.xlabel('Input Size (x100)')
plt.ylabel('Time (second)')
plt.legend(loc='upper left')
plt.title('The worst Case runtime analysis of Fractional Knapsack')

Share this code with others