1. Tutorials
  2. Python Tutorial
  3. How to Implement Fractional Knapsack in Python

How to Implement Fractional Knapsack in Python

Submitted by razormist on Saturday, April 11, 2026 - 23:26.

In this tutorial, we will learn "How to Implement Fractional Knapsack in Python". The main objective is to understand the fractional knapsack problem and its implementation. This guide will walk you step by step through the process, making it easier to follow and apply. By the end of this tutorial, you will have a solid understanding of how fractional knapsack works in Python, helping you strengthen your problem-solving abilities and improve your overall coding skills in data structure implementation.

This topic is straightforward and easy to understand. By following the instructions provided, you will be able to complete it with ease. The program will guide you step by step through the process of implementing Fractional Knapsack. So, let’s dive into the coding process and start implementing the solution to gain a deeper understanding of Python.

Getting Started:

First you will have to download & install the Python IDLE's, here's the link for the Integrated Development And Learning Environment for Python https://www.python.org/downloads/.

Creating Main Function

This is the main function of the application. The following code will display a simple GUI in terminal console that will display program. To do this, simply copy and paste these blocks of code into the IDLE text editor.
  1. def fractional_knapsack(value, weight, capacity):
  2.     index = list(range(len(value)))
  3.     ratio = [v / w for v, w in zip(value, weight)]
  4.     index.sort(key=lambda i: ratio[i], reverse=True)
  5.  
  6.     max_value = 0
  7.     fractions = [0] * len(value)
  8.  
  9.     for i in index:
  10.         if weight[i] <= capacity:
  11.             fractions[i] = 1
  12.             max_value += value[i]
  13.             capacity -= weight[i]
  14.         else:
  15.             fractions[i] = capacity / weight[i]
  16.             max_value += value[i] * fractions[i]
  17.             break
  18.  
  19.     return max_value, fractions
  20.  
  21.  
  22. # MAIN LOOP
  23. while True:
  24.     print("\n============= Implement Fractional Knapsack =============\n")
  25.  
  26.     # Input number of items
  27.     try:
  28.         n = int(input('Enter number of items: '))
  29.         if n <= 0:
  30.             print("Number of items must be positive.")
  31.             continue
  32.     except ValueError:
  33.         print("Invalid input.")
  34.         continue
  35.  
  36.     # Input values
  37.     try:
  38.         value = list(map(int, input(f'Enter {n} values: ').split()))
  39.         if len(value) != n:
  40.             print("You must enter exactly", n, "values.")
  41.             continue
  42.     except ValueError:
  43.         print("Invalid values.")
  44.         continue
  45.  
  46.     # Input weights
  47.     try:
  48.         weight = list(map(int, input(f'Enter {n} weights: ').split()))
  49.         if len(weight) != n:
  50.             print("You must enter exactly", n, "weights.")
  51.             continue
  52.         if any(w <= 0 for w in weight):
  53.             print("Weights must be positive.")
  54.             continue
  55.     except ValueError:
  56.         print("Invalid weights.")
  57.         continue
  58.  
  59.     # Input capacity
  60.     try:
  61.         capacity = int(input('Enter maximum weight: '))
  62.         if capacity < 0:
  63.             print("Capacity cannot be negative.")
  64.             continue
  65.     except ValueError:
  66.         print("Invalid capacity.")
  67.         continue
  68.  
  69.     # Run algorithm
  70.     max_value, fractions = fractional_knapsack(value, weight, capacity)
  71.  
  72.     print(f"\nMaximum value: {max_value}")
  73.     print(f"Fractions taken: {fractions}")
  74.  
  75.     # Try Again Option
  76.     opt = input("\nDo you want to try again? (yes/no): ").strip().lower()
  77.     if opt == "no":
  78.         print("Exiting program...")
  79.         break
  80.     elif opt != "yes":
  81.         print("Invalid choice. Exiting program...")
  82.         break

This Python program implements the Fractional Knapsack algorithm using a greedy approach to maximize the total value within a given weight capacity. It calculates the value-to-weight ratio of each item, sorts them in descending order, and selects items fully or partially based on the remaining capacity. The program runs interactively, allowing users to input item values, weights, and capacity, then outputs the maximum achievable value along with the fraction of each item taken. It also includes input validation and lets users repeat the process or exit.

Output:

There you have it we successfully created How to Implement Fractional Knapsack in Python. I hope that this simple tutorial help you to what you are looking for. For more updates and tutorials just kindly visit this site. Enjoy Coding!

More Tutorials for Python Language

Python Tutorials

Tags
Python
Python codes
Simple Program
fractional