Skip to main content
Code Review

Return to Question

add actual question!
Source Link
Gareth Rees
Gareth Rees
  • 50.1k
  • 3
  • 130
  • 211

Which items does the tourist carry in his knapsack so that their total weight does not exceed 400 decagrams [4 kg], and their total value is maximised?

Which items does the tourist carry in his knapsack so that their total weight does not exceed 400 decagrams [4 kg], and their total value is maximised?

add problem description, programming-challenge tag
Source Link
Gareth Rees
Gareth Rees
  • 50.1k
  • 3
  • 130
  • 211

This is a small solution to the 0/1 knapsack problem from rossetta-codethe knapsack problem from rosettacode.org:

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.

(The list of items, together with their weight in decagrams and their value, is given in the code below.)

My solution is below. This seems almost seems to be too little. Just sort by their efficiency (value/weight) and add the most efficient item until capacity is reached.

This is a small solution to the 0/1 knapsack problem from rossetta-code.

This seems almost seems to be too little. Just sort by their efficiency (value/weight) and add the most efficient item until capacity is reached.

This is the knapsack problem from rosettacode.org:

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.

(The list of items, together with their weight in decagrams and their value, is given in the code below.)

My solution is below. This seems almost seems to be too little. Just sort by their efficiency (value/weight) and add the most efficient item until capacity is reached.

Source Link
cheezsteak
cheezsteak
  • 2.4k
  • 1
  • 17
  • 33

Functional Knapsack Problem in Python

This is a small solution to the 0/1 knapsack problem from rossetta-code.

This seems almost seems to be too little. Just sort by their efficiency (value/weight) and add the most efficient item until capacity is reached.

from itertools import takewhile

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),
    )

def item_efficiency(item):
    name, weight, value = item
    return float(value)/float(weight)

def pack_bag(item):
    name, weight, value = item
    pack_bag.max_weight -= weight
    return pack_bag.max_weight > 0    
pack_bag.max_weight = 400  # static variable implementation

# pack the most efficient item until pack_bag.max_weight is reached.
pack = list(takewhile(pack_bag, reversed(sorted(ITEMS, key=item_efficiency))))

# print output
for item in pack:
    print item[0]

table = zip(*pack)
print "Total Value: %i" % sum(table[2])
print "Total Weight: %i" % sum(table[1])

I understand that this solution doesn't scale if capacity is multidimensional. This gives the correct answer but I haven't seen any solution like it. It could be because I am exporting a lot of the workload to sorted, reversed, and takewhile.