Ali's Photography Space…

[NOTE: To keep the code as simple as we can, We WILL NOT ADD any user input Varevecations. Assuming that our user will Enter the right inputs.]

Definition: The knapsack problem is a Problem in Combinatorial Optimization: Given a set of Items, Each with a Weight and a Value or Profit, We need to Determine the Number of Each Item to Include in a Collection so that the Total Weight is Less than or Equal to a Given Limit and the Total Value is as Large as Possible.
Source: Wikipedia

In this post we will write three Functions, The Main Menu, one to Collect the data and another to solve the problem. So first, let’s see the Main-Menu ..

# Main Menu of the Project
def main_menu ():
    os.system('clear')
    print('\n',' '*5,'******************************')
    print(' '*5,' ***','   Knapsack Problem','   '*1,'***')
    print(' '*5,' ***',' '*22,'***')
    print(' '*5,' ******************************')    
    print('\n',' '*5,"==========[ Main Menu ]==========")
    print(' '*5,' 1. About Knapsack Problem.')
    print(' '*5,' 2. Collect the Items.')
    print(' '*5,' 3. Solve the Problem.')
    print(' '*5,' 9. Exit.')

    user_choice = input("\n   Select from the Menu: > ") 

    return user_choice

Above Menu will display three option that the user can select from:
1. About Knapsack Problem. [To give simple information about what is Knapsack Problem]
2. Collect the Items. [Will ask the user to Enter the Items and their coresponding Weights and Profits.]
3. Solve the Problem. [The user will Enter the Weight limit we have then we will Solve the problem]

Now we will write the Function to collect the Data from the user we will call it def collect_items(): the user will Enter the Item Name, the Weight and the Value or Profit and will save it in a list, then will return it as item_list. Here is the code and run-time screen.

After Collecting the Items, the user can select Number (3) from the Menu to Solve the Knapsack Problem. First we will ask user to Enter the Weights Limit we have, then calculating the Profit over Weight for each Items. In Knapsack we select the Items based on the Max w/p for each and store the indexs in a list, and with each selection we must not exceed the weight limits. Here is the code.. ..

So from the above example, we can achieve the Maximum Profit with weight limits to 50Kg if we take Full Amount of Item a, and Full Amount of Item b and 0.666666666 (0.67) amount of Item c.

1 * 60 = 60
1 * 100 = 100
0.67 * 120 = 80

60 + 100 + 80 = 240

NOTE: The Weight in Knapsack Problem can be weight in kg, or Number/Amount of the item (60 bags, 100 bags ..) or any Unit.

Have fun and do some coding .. 🙂