Python Tutorial

Introduction Python Features Python Applications System requirements for Python Python Installation Python Basics Python Variables Python Data Types Python IDE Python Keywords Python Operators Python Comments Python Pass Statement

Python Conditional Statements

Python if Statement Python elif Statement Python If-else statement Python Switch Case

Python Loops

Python for loop Python while loop Python Break Statement Python Continue Statement Python Goto Statement

Python Arrays

Python Array Python Matrix

Python Strings

Python Strings Python Regex

Python Built-in Data Structure

Python Lists Python Tuples Python Lists vs Tuples Python Dictionary Python Sets

Python Functions

Python Function Python min() function Python max() function Python User-define Functions Python Built-in Functions Anonymous/Lambda Function in Python

Python File Handling

Python File Handling Python Read CSV Python Write CSV Python Read Excel Python Write Excel Python Read Text File Python Write Text File Read JSON File in Python

Python Exception Handling

Python Exception Handling Python Errors and exceptions Python Assert

Python OOPs Concept

OOPs Concepts in Python Classes & Objects in Python Inheritance in Python Polymorphism in Python Python Encapsulation Python Constructor Static Variables in Python Abstraction in Python

Python Iterators

Iterators in Python Yield Statement In Python

Python Generators

Python Generator

Python Decorators

Python Decorator

Python Functions and Methods

Python Built-in Functions Python String Methods Python List Methods Python Dictionary Methods Python Tuple Methods Python Set Methods

Python Modules

Python Modules Python Datetime Module Python Calendar Module  

Python MySQL

Python MySQL Python MySQL Update Operation Python MySQL Delete Operation

Python MongoDB

Python MongoDB

Python Data Structure Implementation

Python Stack Python Queue Python Hash Table Python Graph

Python Advance Topics

Speech Recognition in Python Face Recognition in Python Python Rest API Python Command Line Arguments Python JSON Python Virtual Environment Type Casting in Python Collections in python Python Enumerate Python Debugger Python DefaultDict

Misc

Python PPTX Python Pickle Python Seaborn Python Coroutine Python EOL Python Infinity Python math.cos and math.acos function Python Project Ideas Based On Django Reverse a String in Python Reverse a Number in Python Python Word Tokenizer Python Trigonometric Functions Python try catch exception GUI Calculator in Python Implementing geometric shapes into the game in python Installing Packages in Python Python Try Except Python Sending Email Socket Programming in Python Python CGI Programming Python Data Structures Python abstract class Python Compiler Python K-Means Clustering List Comprehension in Python3 NSE Tools In Python Operator Module In Python Palindrome In Python Permutations in Python Pillow Python introduction and setup Python Functionalities of Pillow Module Python Argmin Python whois Python JSON Schema Python lock Return Statement In Python Reverse a sentence In Python tell() function in Python Why learn Python? Write Dictionary to CSV in Python Write a String in Python Binary Search Visualization using Pygame in Python Latest Project Ideas using Python 2022 Closest Pair of Points in Python ComboBox in Python Python vs R Python Ternary Operators Self in Python Python vs Java Python Modulo Python Packages Python Syntax Python Uses Python Logical Operators Python Multiprocessing Python History Difference between Input() and raw_input() functions in Python Conditional Statements in python Confusion Matrix Visualization Python Python Algorithms Python Modules List Difference between Python 2 and Python 3 Is Python Case Sensitive Method Overloading in Python Python Arithmetic Operators Design patterns in python Assignment Operators in Python Is Python Object Oriented Programming language Division in Python Python exit commands Continue And Pass Statements In Python Colors In Python Convert String Into Int In Python Convert String To Binary In Python Convert Uppercase To Lowercase In Python Convert XML To JSON In Python Converting Set To List In Python Covariance In Python CSV Module In Python Decision Tree In Python Difference Between Yield And Return In Python Dynamic Typing In Python Abstract design pattern in python Builder design pattern in python Prototype design pattern in Python Creational design patterns in Python

How to

How to convert integer to float in Python How to reverse a string in Python How to take input in Python How to install Python in Windows How to install Python in Ubuntu How to install PIP in Python How to call a function in Python How to download Python How to comment multiple lines in Python How to create a file in Python How to create a list in Python How to declare array in Python How to clear screen in Python How to convert string to list in Python How to take multiple inputs in Python How to write a program in Python How to compare two strings in Python How to create a dictionary in Python How to create an array in Python How to update Python How to compare two lists in Python How to concatenate two strings in Python How to print pattern in Python How to check data type in python How to slice a list in python How to implement classifiers in Python How To Print Colored Text in Python How to develop a game in python How to print in same line in python How to create a class in python How to find square root in python How to import numy in python How to import pandas in python How to uninstall python How to upgrade PIP in python How to append a string in python How to open a file in python

Sorting

Python Sort List Sort Dictionary in Python Python sort() function Python Bubble Sort

Programs

Factorial Program in Python Prime Number Program in Python Fibonacci Series Program in Python Leap Year Program in Python Palindrome Program in Python Check Palindrome In Python Calculator Program in Python Armstrong Number Program in Python Python Program to add two numbers Anagram Program in Python Even Odd Program in Python GCD Program in Python Python Exit Program Python Program to check Leap Year Operator Overloading in Python Pointers in Python Python Not Equal Operator Raise Exception in Python Salary of Python Developers in India What is a Script in Python Singleton design pattern in python

Python Knapsack problem

Python Knapsack problem

Before we dig down about Knapsack problems in Python, first let's have a look at what is actually a knapsack problem.

What is a knapsack problem?

A problem from the optimization combinational related issues is known as a knapsack problem. This problem often arises in our daily life in resources allocations where the decisions have to be made from the set of items that are non-divisible tasks or projects which are placed under a fixed budget constraints or time constraint.

Example of knapsack problem

Suppose we have given a set of items; each have a given value (in terms of money on anything) and a given weight such as the total combine weight of items is more than the actual limit. So, here we have to maximize the value within the limit. It means we have to choose the items that have more value and less weight and that's how we can get maximum value within the limit.

This is the classical example of a one-dimensional Knapsack problem.

Note:The word Knapsack itself means a 'bag'.

Knapsack Problem in Python

As of now, we have a basic understanding about the knapsack problems and how a one-dimensional Knapsack problem looks like. Here, in this tutorial, we will discuss about that how we can solve the knapsack problem using Python. We will take 2 example knapsack problems and design a Python program for each to solve them with the dynamic programming. And, after that we will see the explanation of the program to understand the logic and working of it.

  • Important:The knapsack problem (particularly of one-dimension) is referred to as 0/1 knapsack problem in Python and it is the most popular type problem in a dynamically typed programming language.

Now, let's discuss about a 0/1 knapsack problem and approaches we are using to design its solution program in Python. Basically, we use any of the following two approaches to design a solution Python program for any 0/1 knapsack problem:

1. Designing solution program using Brute-force approach

2. Designing solution program using dynamic approach

Let's see their implementation of these approaches.

Given 0/1 knapsack problem

We have a given number of items and these items have their respective weight and value. We have to place these items inside a bag that have a weighing capacity (Let's say W). We have to get the maximum value in the bag from the given items and we have to answer the maximum number of values that we can get in the bag within the limit of it.

Solution 1: Using Brute-force approach in solution program:

 # Define a default knapsack 01 function
 def knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI):
    # Give the initial if conditions
    if NumberOI == 0 or MLimit == 0 :
       return 0
    # Defining nested if condition for higher weight
    if (WeightofItem [NumberOI-1] > MLimit):
       return knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI-1)
    # Using else condition for number of items
    else:
       return max (ValueofItem [NumberOI-1] + knapsack01 (MLimit-WeightofItem [NumberOI-1], WeightofItem, ValueofItem, NumberOI-1),
          knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI-1))
 # Defining variables used in the function
 ValueofItem = [5, 10, 20, 50, 100, 200, 500, 2000]
 WeightofItem = [1, 4, 8, 16, 24, 32, 36, 40]
 NumberOI = len (ValueofItem)
 # Taking maximum limit as user input
 MLimit = int (input ("Enter the maximum limit for the bag: "))
 # Printing result of problem in the output
 print ("The maximum value of items we can get with the given limit: ")
 print (knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI)) 

Output:

 Enter the maximum limit for the bag: 97
 The maximum value of items we can get with the given limit:
 2565 

Explanation:

 In this program, we have implemented the brute-force approach for the solution of given problem. We have defined a knapsack function and give variables of the problems i.e., Maximum limit of bag, Weight of each item, Value of each item and Number of items, as the arguments in this function.

Then, we used nested if else condition in the function with the given variables to apply the brute-force approach in the program.

We get maximum value and all the findings in this nested if else condition. After that, we have defined the values of the given variables in function i.e., Values of items, Weight of items and number of items respectively in list format.

After that, we defined the maximum limit of the bag variable to user input. After that, we called out the function to print the result as maximum value can be stored in bag. When the program will get the maximum limit of bag as user input, the result for maximum value in the bag with respect to maximum limit, will be printed in the output.

Solution 2: Using dynamic approach in solution program:

 # Define a default knapsack 01 function
 def knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI):
    M = [ [0 for a in range (MLimit + 1)] for a in range (NumberOI + 1)]
    # Define a for loop for limit
    for b in range (NumberOI + 1):
       # Nested for loop for higher limit
       for c in range (MLimit + 1):
          # Defining if condition for maximum weight
          if b == 0 or c == 0:
             M[b][c] = 0
          # Elseif condition for maximum value in bag
          elif WeightofItem[b-1] <= c:
             M[b][c] = max (ValueofItem[b-1] + M[b-1][c-WeightofItem[b-1]], M[b-1][c])
          else:
             M[b][c] = M[b-1][c]
    return M[NumberOI][MLimit] # returning maximum value from the function
 # Defining variables used in the function
 ValueofItem = [5, 10, 20, 50, 100, 200, 500, 2000]
 WeightofItem = [1, 4, 8, 16, 24, 32, 36, 40]
 NumberOI = len (ValueofItem)
 # Taking maximum limit as user input
 MLimit = int (input ("Enter the maximum limit for the bag: "))
 # Printing result of problem in the output
 print ("The maximum value of items we can get with the given limit: ")
 print (knapsack01 (MLimit, WeightofItem, ValueofItem, NumberOI)) 

Output:

 Enter the maximum limit for the bag: 69
 The maximum value of items we can get with the given limit:
 2115 

Explanation –

In this program, after defining the knapsack function we used the dynamic approach in the function.

We used nested for loop with the arguments of the function. In the nested for loop, we have defined a nested if else condition.

We used variables in the elseif and if condition to get the maximum value result. Then, we have defined variable values in list format and get the user input of maximum limit. We get the result of maximum value of bag using dynamic approach after giving maximum limit of bag as user input.

Conclusion:

In this tutorial, we learned about knapsack problem. We learned about knapsack 0/1 problem in Python. We also learned about the both approaches i.e., brute-force approach & dynamic approach, that we use in our Python program to solve the knapsack 0/1 problem.



ADVERTISEMENT
ADVERTISEMENT