Find subset with largest talent to weight ratio, subject to minimum weight

Question

I'm using some old USA Computing Olympiad (USACO) problems to help teach me programming. This is the second one I've posted, I hope that's okay -- let me know if this is considered abusing the system.

You can find my first post here. As noted there, I'm essentially a beginner at programming in general, so any suggestions you have to improve any aspect of the code will be helpful. I tried to implement the suggestions of Gareth and Peter from the last thread as I worked on this problem.

This is the "Talent Show" problem:

Farmer John is bringing his \$N\$ cows, conveniently numbered \$1,\ldots, N\$, to the county fair, to compete in the annual bovine talent show! His \$i\$th cow has a weight \$w_i\$ and talent level \$t_i,\$ both integers. Upon arrival, Farmer John is quite surprised by the new rules for this year's talent show:

1. A group of cows of total weight at least \$W\$ must be entered into the show(in order to ensure strong teams of cows are competing, not just strong individuals), and
2. The group with the largest ratio of total talent to total weight shall win.

FJ observes that all of his cows together have weight at least \$W,\$ so he should be able to enter a team satisfying (1). Help him determine the optimal ratio of talent to weight he can achieve for any such team.

Input Format

The first line of input contains \$N\$ (\$1 \le N \le 250 \$) and \$W\$ (\$1 \le W \le 1000\$). The next \$N\$ lines describe a cow with two integers \$w_i\$ and \$t_i.\$

Output Format

Output \$\lfloor 1000A\rfloor\$ where \$A\$ is the largest possible talent ratio Farmer John can achieve with cows having weight at least \$W.\$

Sample input

3 15
20 21
10 11
30 31

Sample Output

1066

The algorithm is a bit hard to follow, so I'm also curious if my code got across what's going on or not. I started the problem by drawing this picture on paper, which hopefully sheds some light on what I'm trying to do with the code.

(Note that when I actually started coding, I realized it was a lot of work for zero gain to keep track of the second index so I dropped it.)

import glob


def check_possible(talent_ratio, cow_list, min_weight):
    """ 
    check if the talent ratio possible with the min weight given the cow list 

    Note that talent_ratio is possible if there is some set of cows with total 
    weight at least min_weight and SUM (talent - talent_ratio*weight) >= 0 

    We use a knapsack like algorithm to keep track of this

    ------- 

    Inputs:
    talent_ratio is an integer expressing the ratio of talent we want to check
    min_weight is an integer expressing how large we force the weight to be
    cow_list is the list of cows should be a list of tuples (weight, talent)

    Return: 
    true if the talent ratio is achievable 
    false otherwise 
    """

    #max_talent[total_weight] will keep track of the the maximum value of 
    #               SUM (talent - talent_ratio*weight) 
    #among all sets of cows with total weight exactly total_weight
    #
    #max_talent[min_weight] represents the maximum value of
    #           SUM (talent - talent_ratio*weight) 
    #among all sets of cows with total weight at least min_weight
    max_talent = ["no_value" for total_weight in range(min_weight+1)]

    max_talent[0] = 0
    number_cows = len(cow_list)

    #Knapsack type algorithm to compute max_talent[total_weight]
    for cow in range(number_cows):
        talent = cow_list[cow][1]
        weight = cow_list[cow][0]
        value = talent - talent_ratio*weight 
        for heaviness in range(min_weight,-1,-1): 
        #loop backwards to avoid using individual cows more than once. 
        #For example, say our max_talent[1] was 10 cow 1. 
        #this would be computed at heaviness=0. 
        #But then at heaviness=1 we add cow 1's max talent again,
        #giving max_talent[2] = 20, but using cow 1 twice.
            new_weight = min(heaviness+weight, min_weight) 
            #only update if there's a value already for heaviness
            if max_talent[heaviness] != "no_value": 
                if max_talent[new_weight] == "no_value": 
                    max_talent[new_weight] = max_talent[heaviness]+value
                elif max_talent[heaviness]+value > max_talent[new_weight]: 
                    max_talent[new_weight] = max_talent[heaviness]+value
    return max_talent[min_weight] >= 0

def process_inputs(data): 
    """
    Take the input data from file and turn it into a list of lists of ints, 
    and two ints telling us how many cows we have and the min weight. 

    -------

    Inputs:
    data is a file object.

    Returns: 
    num_cows -- the number of cows we have in total, an INT
    min_weight -- the minimum weight our cows must have, an INT
    cow_list -- A list of tuples representing cows. 
           Each tuple describes a cow by (weight, talent)
    """
    lines = data.readlines()
    #turn the lines into a list of list ints
    cow_list=[list(map(int,line.split())) for line in lines]
    num_cows, min_weight = cow_list[0]
    cow_list.pop(0)

    return num_cows, min_weight, cow_list

inputs = glob.glob("*.in")

for input in inputs: 
    with open(input) as data:
        num_cows, min_weight, cow_list = process_inputs(data)
        max_talent = 0

        #binary search through possible values of floor(1000*max_talent)
        top = int(1000*max([cow[1]/cow[0] for cow in cow_list]))
        bottom = 0
        while(top > bottom + 1): 
            middle = int((top + bottom)/2)
            if check_possible(middle/1000, cow_list, min_weight):
                bottom = middle
            else: 
                top = middle 

        max_talent = bottom
        print(max_talent)

Answer 1

1. Review

1. The code would be easier to test if there were a function with a specification like this:

   def max_talent_to_weight_ratio(min_weight, cow_list):
       """Return the maximum of int(1000 * sum(talent) / sum(weight)) for a
       subset of cows with total weight at least min_weight, each cow
       being represented as a pair (weight, talent).
   
       """
   

   Then it would be easy to run test cases:

   >>> max_talent_to_weight_ratio(15, [(20, 21), (10, 11), (30, 31)])
   1066
   

2. Instead of looking up the elements of a tuple by number:

   talent = cow_list[cow][1]
   weight = cow_list[cow][0]
   

   use tuple assignment:

   weight, talent = cow_list[cow]
   

3. Instead of iterating over the indexes into a list:

   number_cows = len(cow_list)
   for cow in range(number_cows):
       # code using cow_list[cow]
   

   iterate over the elements of the list directly:

   for cow in cow_list:
       # code using cow
   

   or better still, combine this with tuple assignment:

   for weight, talent in cow_list:
   

4. When iterating backwards:

   for heaviness in range(min_weight,-1,-1):
   

   it's often clearer to use reversed:

   for heaviness in reversed(range(min_weight + 1)):
   

5. I think a name like old_weight would be clearer than heaviness.

6. Where the code has two conditions but both of the bodies are the same:

   if max_talent[new_weight] == "no_value":
       max_talent[new_weight] = max_talent[heaviness]+value
   elif max_talent[heaviness]+value > max_talent[new_weight]: 
       max_talent[new_weight] = max_talent[heaviness]+value
   

   the two conditions can be combined into one, using or:

   new_value = max_talent[old_weight] + value
   if (max_talent[new_weight] == "no_value"
       or new_value > max_talent[new_weight]):
       max_talent[new_weight] = new_value
   

7. The need for the special case of "no_value" can be avoided by representing max_talent as a mapping from total weight to value (instead of a list), like this:

   # Mapping from total weight to maximum value.
   max_talent = {0: 0}
   

   And then the lack of a value corresponds to the lack of a key in the mapping:

   if old_weight in max_talent:
       new_value = max_talent[old_weight] + value
       if (new_weight not in max_talent
           or new_value > max_talent[new_weight]):
           max_talent[new_weight] = new_value
   

   But now the need to test new_weight not in max_talent can be avoided by using collections.defaultdict:

   # Mapping from total weight to maximum value.
   max_talent = defaultdict(lambda:0)
   max_talent[0] = 0
   

   and then:

   if old_weight in max_talent:
       max_talent[new_weight] = max(max_talent[new_weight], max_talent[old_weight] + value)
   

8. There is nothing about the problem that is specific to cows, so I think it would be less distracting for the reader if the code used abstract terminology. I would use "item" instead of "cow" and "score" instead of "talent".

2. Improved algorithm

Before working on an algorithm like this it's worth doing a bit of analysis to see if there are any properties of the solution that might come in useful.

Let's start with some notation. Suppose that \$I\$ is a team (a set of cows). Define \$W(I) = \sum_{i∈I} w_i\$ to be the total weight of the team, \$T(I) = \sum_{i∈I} t_i\$ to be the total talent of the team, and \$R(I) = {T(I) \over W(I)}\$ to be the ratio of total talent to total weight of the team.

Write \$w\$ for the minimum total weight needed to win, and say that a team \$I\$ is "winning" if \$W(I) ≥ w\$ and \$R(I)\$ is the maximum among all teams meeting the weight requirement. Note that there might be multiple winning teams if several teams have the same ratio.

Let \$J\$ be the winning team with the smallest total weight. Consider the weakest cow in the team, that is, the cow \$j∈J\$ with the smallest value of \$R(\{j\})\$, and let \$J′ = J \setminus \{j\}\$ be the team with \$j\$ removed.

Now either \$J′\$ is empty, in which case \$W(J′) = 0 < w\$ and so \$J′\$ is not a winning team, or else \$J′\$ is non-empty, in which case \$R(J′) ≥ R(J)\$, since \$j\$ was the weakest cow and so removing it improves the overall talent-to-weight ratio. In the latter case it follows that \$W(J′) < w\$, otherwise \$J′\$ would be a winning team with a smaller total weight, contrary to hypothesis.

What this means is that there exists a winning team with the property that we can't remove the weakest cow from the team without going under the minimum total weight. And this means that if we follow the dynamic programming approach, but taking the cows in descending order of their talent-to-weight ratio, then we can never need to add another cow to a team that is already at or over the minimum weight. (Because such a cow would be the weakest cow in the new team, and so could be removed without hurting the team as explained above.)

This means that we avoid the need for the adjustment of the talent (value = talent - talent_ratio*weight): we can just store the total talent. And more importantly, we avoid the need for a binary search, since just one application of the knapsack algorithm finds the result.

3. Revised code

from collections import defaultdict
from fractions import Fraction
from itertools import product

def max_score_to_weight_ratio(min_weight, items):
    """Return the maximum of sum(score) / sum(weight) for a subset of
    items with total weight at least min_weight, each item being
    represented as a pair (weight, score).

    """
    # Sort items into descending order by score-to-weight ratio.
    items = sorted(items, key=lambda it: Fraction(it[1], it[0]), reverse=True)

    # Mapping from total weight to best (maximum) total score for a
    # subset of items with that weight.
    best = defaultdict(lambda:0)
    best[0] = 0

    for (w, s), old_w in product(items, reversed(range(min_weight))):
        if old_w in best:
            new_w = old_w + w
            best[new_w] = max(best[new_w], best[old_w] + s)

    return max(Fraction(s, w) for w, s in best.items() if w >= min_weight)

Notes

1. This implementation returns the best ratio itself, not int(1000 * ratio). The reason for doing it this way is that the former is easy to explain, and the latter is an artificial condition of the USACO challenge, and not inherent to the problem. It would be easy enough to add a small wrapper function for the actual challenge if you needed to.

2. The ratios are represented as fractions using the fractions.Fraction class. This avoids the need to worry about possible loss of precision when doing floating-point division: a fraction object represents an exact ratio of integers.

3. The code uses itertools.product to combine two loops into one. This saves a level of indentation.

4. I've abbreviated variable names within loops in order to keep expressions on one line and to make the structure of the code clear. This kind of abbreviation would be a poor idea in a large block of code, but within a loop of four lines I think it's easy enough to remember that w represents weight and s represents score.