python
Dashboard
My Repos
Compilers
Python Online
Node JS Online
Golang Online
codepy
Login
My Repos
Sign Out
Online Python Interpreter
Stop
Run
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
Public
Clear
My Repos
Repo
Lang
Login
Register
Login
Create a free account. No Credit card info required.
I agree with the Codepy
Term of Service
Sign Up