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:
- 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
- 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.
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 \$\lfloor 1000A\rfloor\$ where \$A\$ is the largest possible talent ratio Farmer John can achieve with cows having weight at least \$W.\$
3 15 20 21 10 11 30 31
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 number_cows = len(cow_list) #Knapsack type algorithm to compute max_talent[total_weight] for cow in range(number_cows): talent = cow_list[cow] weight = cow_list[cow] 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 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 = 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 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/cow 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)