Return to Answer

So even in small examples like this, you really do need to use the tabular method (aka "dynamic programming") to get the best answer. See this answer for one way to implement it in Python.

So even in small examples like this, you really do need to use the tabular method (aka "dynamic programming") to get the best answer. See this answer for one way to implement it in Python.

1. There's no documentation. What do your functions do, what arguments do they take, and what do they return?

2. The code is not portable to Python 3.

3. Your program has code at the top level, which makes it inconvenient to test from the interactive interpreter, because as soon as you import the module the code runs. Better to encapsulate the top-level code within a function.

4. Your program uses a global variable, pack_bag.max_weight. Global variables make code inconvenient to test, because you have to get the globals into the right state before running each test case. It is more convenient (and more robust) to encapsulate all the state you need inside a function or object.

5. In item_efficiency you don't use the name of the item. It's conventional to indicate unused values in tuple unpacking by using the name _. Alternatively, you could use a collections.namedtuple and then you'd be able to write item.weight and item.value.

6. As noted by Janne Karila in comments, itertools.takewhile stops as soon as it encounters an item for which pack_bag returns False, but there might be (less efficient, but lighter) items which can still be packed. This could be fixed by using filter instead of takewhile.

from collections import namedtuple
Item = namedtuple('Item', 'name weight value'.split())
ITEMS = [
 Item("map", 9, 150),
 Item("compass", 13, 35),
 Item("water", 153, 200),
 Item("sandwich", 50, 160),
 Item("glucose", 15, 60),
 Item("tin", 68, 45),
 Item("banana", 27, 60),
 Item("apple", 39, 40),
 Item("cheese", 23, 30),
 Item("beer", 52, 10),
 Item("suntan cream", 11, 70),
 Item("camera", 32, 30),
 Item("t-shirt", 24, 15),
 Item("trousers", 48, 10),
 Item("umbrella", 73, 40),
 Item("waterproof trousers", 42, 70),
 Item("waterproof overclothes", 43, 75),
 Item("note-case", 22, 80),
 Item("sunglasses", 7, 20),
 Item("towel", 18, 12),
 Item("socks", 4, 50),
 Item("book", 30, 10),
 ]
def efficiency(item):
 """Return efficiency of item (it's value per unit weight)."""
 return float(item.value) / float(item.weight)
def packing(items=ITEMS, max_weight=400):
 """Return a list of items with the maximum value, subject to the
 constraint that their combined weight must not exceed max_weight.
 """ 
 def pack(item):
 # Attempt to pack item; return True if successful.
 if item.weight <= pack.max_weight:
 pack.max_weight -= item.weight
 return True
 else:
 return False
 pack.max_weight = max_weight
 return list(filter(pack, reversed(sorted(items, key=efficiency))))

1. There's no documentation. What do the functions do, what arguments do they take, and what do they return?

2. The code is not portable to Python 3.

3. The program has code at the top level, which makes it inconvenient to test from the interactive interpreter, because as soon as it imports the module the code runs. Better to encapsulate the top-level code within a function.

4. The program uses a global variable, pack_bag.max_weight. Global variables make code inconvenient to test, because you have to get the globals into the right state before running each test case. It is more convenient (and more robust) to encapsulate all the state inside a function or object.

5. item_efficiency doesn't use the name of the item. It's conventional to indicate unused values in tuple unpacking by using the name _. Alternatively, you could use a collections.namedtuple and then you'd be able to write item.weight and item.value.

6. Use sorted(..., reverse=True) rather than reversed(sorted(...)).

7. As noted by Janne Karila in comments, itertools.takewhile stops as soon as it encounters an item for which pack_bag returns False, but there might be (less efficient, but lighter) items which can still be packed. This could be fixed by using filter instead of takewhile.

from collections import namedtuple
Item = namedtuple('Item', 'name weight value'.split())
ITEMS = [
 Item("map", 9, 150),
 Item("compass", 13, 35),
 Item("water", 153, 200),
 Item("sandwich", 50, 160),
 Item("glucose", 15, 60),
 Item("tin", 68, 45),
 Item("banana", 27, 60),
 Item("apple", 39, 40),
 Item("cheese", 23, 30),
 Item("beer", 52, 10),
 Item("suntan cream", 11, 70),
 Item("camera", 32, 30),
 Item("t-shirt", 24, 15),
 Item("trousers", 48, 10),
 Item("umbrella", 73, 40),
 Item("waterproof trousers", 42, 70),
 Item("waterproof overclothes", 43, 75),
 Item("note-case", 22, 80),
 Item("sunglasses", 7, 20),
 Item("towel", 18, 12),
 Item("socks", 4, 50),
 Item("book", 30, 10),
 ]
def efficiency(item):
 """Return efficiency of item (its value per unit weight)."""
 return float(item.value) / float(item.weight)
def packing(items=ITEMS, max_weight=400):
 """Return a list of items with the maximum value, subject to the
 constraint that their combined weight must not exceed max_weight.
 """ 
 def pack(item):
 # Attempt to pack item; return True if successful.
 if item.weight <= pack.max_weight:
 pack.max_weight -= item.weight
 return True
 else:
 return False
 pack.max_weight = max_weight
 return list(filter(pack, sorted(items, key=efficiency, reverse=True)))