У меня проблема с выводом в рюкзак проблема - PullRequest
Новая
       49

У меня проблема с выводом в рюкзак проблема

0 голосов
/ 04 августа 2020

Я написал код, но он не работает с некоторыми значениями. Я использовал значения 1 10 500 30 (результат 166,666 ...) и 3 50 60 20 100 50 120 30 (правильный ответ 180, но я получил 0,0000) Вот мой код. 

import sys

def get_optimal_value(capacity, weights, values):
    value = 0.
    arr= [0]*len(weights)
    mass = [values[i]/weights[i] for i in range(len(weights))]
    i = 1
    a = 0
    for i in range(len(weights)):
        if capacity == 0:
            return 0
        if  weights[mass.index(max(mass))] > 0:
            a = min(weights[mass.index(max(mass))],capacity)
            value = value + a * max(mass)
            weights[mass.index(max(mass))] = weights[mass.index(max(mass))] - a
            arr[i] = arr[i] + a
            capacity = capacity - a
            mass[mass.index(max(mass))] = -1
    return value


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))
...