Python program to implement Knapsack using Greedy Approach (Binary & Fractional)

# Knapsack using Greedy Approach (Binary & Fractional)

A=[]
w=0
n=0

class KP:
    item=0
    weight=0
    value=0
    valueIndex=0.0
    select=0.0

def getData():
    global A
    global w
    global n    

    w=int(input("\nEnter Knapsack Capacity: "))
    n=int(input("Enter number of items: "))
    for i in range(n):
        A.append(KP())

    for i in range(n):
        print("\tItem",i+1)
        A[i].item=i+1
        A[i].weight=int(input("Enter weight of item: "))
        A[i].value=int(input("Enter value of item: "))

        A[i].valueIndex= A[i].value / A[i].weight
        A[i].select=0
    

def showData():
    global A
    global w
    global n    

    print("\n____ Given Inputs ____")
    print("\nKnapsack capacity: ",w)
    print("\nItem\tWeight\tValue")
    print("-----\t------\t------")
    for i in range(n):
        print("\n",A[i].item,"\t",A[i].weight,"\t",A[i].value)


def  bSort(): # Bubble sort with respect to value index
    global A
    global w
    global n    

    flag=1
    for i in range(n):
        if flag==1:
            flag=0
            for j in range(n-1):
                if A[j].valueIndex < A[j+1].valueIndex:
                    # Swapping A[j] and A[j+1]

                    temp=KP()
                    temp=A[j]
                    A[j]=A[j+1]
                    A[j+1]=temp
                    flag=1


def output():
    # Displaying optimal solution
    global A
    global w
    global n    

    print("Selected items for Optimal solution are: ",end="")
    for i in range(n):
        if A[i].select==1:
            print("\t",A[i].item,end="")
    print("\n")


# __________________________ Binary Knapsack __________________________
def  binaryKnapsack():
    global A
    global w
    global n    

    bSort()
    print("\n\n\t____ Binary Knapsack ____\n")
    print("\nKnapsack capacity: ",w)
    print("\nItem\t\tWeight\t\tRemaining\tProfit")
    print("\nSelected\t\t\tWeight")
    print("\n-----\t\t------\t\t------\t\t------")

    remainingWeight=w
    sum_value=0
    for i in range(n):
        if A[i].weight <= remainingWeight:
            sum_value+=A[i].value
            remainingWeight-=A[i].weight
            A[i].select=1
            print("\n",A[i].item,"\t\t",A[i].weight,"\t\t",remainingWeight,"\t\t",A[i].value)
     
    print("\n______________________________________________________")
    print("\nTotal Profit= ",sum_value,"\n")
    output()


# __________________________ Fractional Knapsack __________________________
def minimum(x, y):
    if x < y:
        return x
    else:
        return y

def fractionalKnapsack():
    global A
    global w
    global n    

    bSort()
    print("\n\n\t____ Fractional Knapsack ____\n")
    print("\nKnapsack capacity: ",w)
    print("\nItem\t\tWeight\t\tFraction\tWeight\t\tProfit")
    print("\nselected\tremaining\tselected\ttaken")
    print("\n-------\t\t-------\t\t-------\t\t-------\t\t-------")

    remainingWeight=w
    sum_value=0
    for i in range(n):
        if remainingWeight != 0:
            m=minimum(A[i].weight,remainingWeight)
            frac=(m*1.0)/(A[i].weight*1.0)

            w1=A[i].weight*frac

            value1=A[i].value * frac

            remainingWeight-=w1
            sum_value+=value1

            A[i].select=frac
            print("\n",A[i].item,"\t\t",remainingWeight+w1,"\t\t",frac,"\t\t",w1,"\t\t",value1)

    print("\n_______________________________________________________________________")
    print("\nTotal Profit= ",sum_value,"\n")
    output()


# __________________________ Main Block Starts __________________________
print("\t\t\t____Knapsack using Greedy Approach (Binary & Fractional)____")

getData()
showData()

print("\n\n\t1. Binary Knapsack\t2. Fractional Knapsack")
ch=int(input("\tEnter your choice: "))

if ch==1:
    binaryKnapsack()
elif ch==2:
    fractionalKnapsack()
else:
    print("Wrong Choice!")

Output