1
\$\begingroup\$
def get_optimal_value(capacity, weights, values):
    value = 0.
    remaining_capacity = capacity
    # compute value per unit
    values_per_unit = [v / float(w) for w, v in zip(weights, values)]
    while remaining_capacity > 0:
        value_and_index = get_max_value_per_unit(values_per_unit)
        replace_max_value(values_per_unit, value_and_index["index"])

        weight = weights[value_and_index["index"]]
        value_per_unit = value_and_index["value"]

        if remaining_capacity >= weight:
            remaining_capacity = remaining_capacity - weight
            value = value + (weight * value_per_unit)
        elif remaining_capacity < weight:
            value = value + (min(remaining_capacity, weight) * value_per_unit)
            acceptable_capacity = min(remaining_capacity, weight)
            remaining_capacity = remaining_capacity - acceptable_capacity
    return value


def get_max_value_per_unit(values_per_unit):
    idx = values_per_unit.index(max(values_per_unit))
    value = values_per_unit[idx]
    return {'value': value, 'index': idx}

def replace_max_value(values_per_unit, idx):
    values_per_unit[idx] = -1

if __name__ == "__main__":
    data = list(map(int, sys.stdin.read().split()))
    n, capacity = data[0:2]
    values = data[2:(2 * n + 2):2]
    weights = data[3:(2 * n + 2):2]
    opt_value = get_optimal_value(capacity, weights, values)
    print("{:.10f}".format(opt_value))

Input:

5 100
60 20
100 50
120 30
90  10
10  10

Run:

python [filename].py < input.txt

Question:

The goal of the algorithm above, is to make sure the knapsack has the highest value. Can we further improve the implementation above?

\$\endgroup\$
2
\$\begingroup\$

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

Used as:

replace_max_value(values_per_unit, value_and_index["index"])

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

Regarding that 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
    return new_list

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.

Sort!!

In cases like this sorting is your friend. Before starting your loop take your values_per_unit and sort it.

sort_indexes = reversed( [i[0] for i in sorted(enumerate(values_per_unit), key=lambda x:x[1])] )
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:
        break

return value

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.