RosettaCode- Knapsack problem created by tapicella - https://repl.it/HtMj/28

RosettaCode- Knapsack problem.py

'''
http://rosettacode.org/wiki/Knapsack_problem/0-1

Knapsack problem/0-1

A tourist wants to make a good trip at the weekend with his friends.

They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip.

He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it,   and it will have to last the whole day.

He creates a list of what he wants to bring for the trip but the total weight of all items is too much.

He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip. 

map 	                  9 	150
compass 	              13 	35
water 	                153 200
sandwich 	              50 	160
glucose 	              15 	60
tin 	                  68 	45
banana 	                27 	60
apple 	                39 	40
cheese 	                23 	30
beer 	                  52 	10
suntan cream 	          11 	70
camera 	                32 	30
T-shirt 	              24 	15
trousers 	              48 	10
umbrella 	              73 	40
waterproof trousers 	  42 	70
waterproof overclothes 	43 	75
note-case 	            22 	80
sunglasses 	            7 	20
towel 	                18 	12
socks 	                4 	50
book 	                  30 	10 
'''

def costAnalysis(items):
  value_to_cost = []
  for i in items:
    value_to_cost.append((i[0], float(i[1]), float(i[2])/float(i[1])))
  value_to_cost.sort(key=lambda x: x[2], reverse=True)
  return value_to_cost
  
def parseInput(s):
  result = []
  l = s.split('\n')
  for i in l:
    isplit = i.split(' ')
    result.append(isplit)
  return result

def getItems(items):
  total_weight = 0 
  total_value = 0
  results = []
  names = []
  for item in items:
    if item[1]+total_weight <= 400:
      results.append(item)
      names.append(item[0])
      total_weight+=(item[1])
      total_value+=(item[1]*item[2])
    else:
      continue
  return (names, total_weight, total_value)
      
      

#Source very unhelpful with data input   
items = '''map 9 150
compass 13 35
water 153 200
sandwich 50 160
glucose 15 60
tin 68 45
banana 27 60
apple 39 40
cheese 23 30
beer 52 10
suntan-cream 11 70
camera 32 30
T-shirt 24 15
trousers 48 10
umbrella 73 40
waterproof-trousers 42 70
waterproof-overclothes 43 75
note-case 22 80
sunglasses 7 20
towel 18 12
socks 4 50
book 30 10'''

item_list = parseInput(items)
costs = costAnalysis(item_list)
print(getItems(costs))