#Fractional knapsack

class Item:
    def __init__(self,value,weight,name):
        self.value = value
        self.weight = weight
        self.name = name
        self.fraction = 0

green = Item(10,12.,'green')
blue = Item(4,2.,'blue')
gray = Item(2,1.,'gray')
red = Item(1,1.,'red')
yellow = Item(2,4.,'yellow')
allitems = [green,blue,gray,red,yellow]
c = 15. #Capacity

#Finding value over weight
for item in allitems:
    item.valueoverweight = float(item.value)/item.weight


#Creating a dictionary to make it easier to get each item
allitemstemp = allitems[:]

#Greedy algorithm
knapsack = []
while sum([item.weight*item.fraction for item in knapsack]) < c:
    largest = max([item.valueoverweight for item in allitemstemp])
    bitem = [item for item in allitemstemp if item.valueoverweight==largest][0]
    allitemstemp.remove(bitem)
    if (bitem.weight + sum([item.weight for item in knapsack])) < c:
        bitem.fraction = 1
        knapsack.append(bitem)
    else:
        cleft = c - sum([item.weight for item in knapsack])
        bitem.fraction = cleft / bitem.weight
        knapsack.append(bitem)
print 'The folliwing items are in the knapsack:'
print 'Item\tvalue\tweight\tvalue/weight\tfraction'
for item in knapsack:
    print item.name,'\t',item.value,'\t',item.weight,'\t',item.valueoverweight,'\t',item.fraction       

#Not in the knapsack
for item in allitemstemp:
    print item.name,'\t',item.value,'\t',item.weight,'\t',item.valueoverweight,'\t',item.fraction