I think some better organization will help. Also, a slightly different algorithm will help simplify.
Separation of concerns (e.g. code splitting)
I think the way you have split everything up could use some work. You only split out two bits of functionality to separate functions, and both are so simple they would probably just be better off inline. This one in particular:
def replace_max_value(values_per_unit, idx):
values_per_unit[idx] = -1
This total combination is much more verbose then simply doing it inline:
values_per_unit[value_and_index['index']] = -1
The same is really true for your other method,
get_max_value_per_unit. To be clear, I'm not saying that you shouldn't split up parts of your program into separate functions. However, splitting a single line (or even just three lines) is usually a sign of choosing the wrong "seams" to break up your application on, unless that functionality is needed in different places. Obviously, that isn't the case here.
Although, this is simple enough that you might not really have to break anything apart, especially after some simplifications (coming soon). The division between your
__main__ calling function and your
get_optimal_value is probably sufficient.
Separate input and output
replace_max_value() method, even though it should go away, there is another lesson here. I'm generally not a fan of using function parameters for output. I.e., you are relying upon pythons pass-by-reference style to modify the passed in list. As a general rule of thumb this is often error-prone in the long run. Having a return value makes it clear what is getting modified and when it is being modified, but relying on modification of a function parameter is much less obvious. As a result, it is easy to come back later and get confused about how/where your
values_per_unit variable is being modified. This syntax, however, is much more clear (even if more verbose):
values_per_unit = set_max_value( values_per_unit, value_and_index['index'] )
It is obvious exactly what is input, and what is being changed. Now with python this is mildly trickier because you have no choice but to pass-by-reference, but a simple copy operation fixes the issue:
def set_max_value( values_per_unit, idx ):
new_list = list( values_per_unit )
new_list[idx] = -1
Granted, this is slightly slower (because of the array copy), but unless performance is known to be an issue, I think it is better for long-term code maintenance to do the copy and have a clear input/output for your function.
In cases like this sorting is your friend. Before starting your loop take your
values_per_unit and sort it.
sort_indexes = reversed( [i for i in sorted(enumerate(values_per_unit), key=lambda x:x)] )
weights = [ weights[i] for i in sort_indexes ]
values = [ values[i] for i in sort_indexes ]
values_per_unit = [ values_per_unit[i] for i in sort_indexes ]
for ( weight, value, value_per_unit ) in zip( weights, values, values_per_unit ):
weight_to_use = min( weight, remaining_capacity )
remaining_capacity -= weight_to_use
value += weight_to_use*value_per_unit
if remaining_capacity <= 0:
Although it is worth noting that I am looping over
sort_indexes three times. Some might prefer doing that with one loop for performance, but I find this easier to read, and would stick to it as long as I knew performance wasn't going to be a big concern.