0
\$\begingroup\$

I wrote this in order to solve the fractional knapsack problem. Any feedback is appreciated.

def get_optimal_value(capacity, weights, values):
    value = 0.
    if sum(weights) <= capacity:
        return sum(values)
    if len(weights) == 1:
        value = values[0]/float(weights[0])*capacity
    densities = [(v/float(w), w) for (v,w) in zip(values, weights)]
    densities = sorted(densities, key=lambda density:density[0], reverse=True)
    fraction = 0.
    #print(densities)
    for i in range(len(weights)):
        fraction = sum([f for (d,f) in densities[0:i]])
        #print(i, fraction, capacity)
        if fraction >capacity and i >0:
            value = sum([d*f for (d,f) in densities[0:i-1]]) + densities[i][0]*(1.0000000-densities[i][1]/float(capacity))*capacity
        if fraction == capacity and i >0:
            value = sum([d*f for (d,f) in densities[0:i]])

    return value
\$\endgroup\$

closed as off-topic by Gareth Rees, Mast, Peilonrayz, Malachi, SuperBiasedMan May 12 '16 at 13:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Gareth Rees, Mast, Peilonrayz, Malachi, SuperBiasedMan
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ This program does not solve the problem (see my answer for details). So I am voting to close. \$\endgroup\$ – Gareth Rees May 12 '16 at 9:37
  • \$\begingroup\$ Essentially, if my solution had worked, I would not need feedback, and would not have asked for code review. \$\endgroup\$ – polka May 12 '16 at 17:38
1
\$\begingroup\$

The program does not solve the problem:

>>> get_optimal_value(1, (1, 1, 1, 1), (1, 1, 1, 1))
2.0

Here we have a knapsack with capacity 1, and four kinds of item, each with weight 1 and value 1. So all ways of filling the knapsack have value 1.

\$\endgroup\$
  • \$\begingroup\$ i appreciate that i had not considered that scenario, and you have pointed it out to me. \$\endgroup\$ – polka May 12 '16 at 17:35

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