Задача на python

[Huobase]

Есть
переменная 'a[n[]]', где n[0] - объем , n[1] - Коэффициент
Напишите код, который рассчитает объем v,
чтобы общий коэффициент был максимальным.


a = [[6, 12], [2, 25], [431, 150], [10, 100], [55, 41]
v = 70
Желательно, чтобы задача решалась при любых числах

[Arigato]

Сообщение от Huobase

Желательно, чтобы задача решалась при любых числах

Да, хорошо бы. Но где ваши попытки?

[BDA]

Из такого описания не пойму смысл задачи. Почему в примере ответ 70, а не 431 (объем с самым большим коэффициентом) или 504 (сумма объемов с положительными коэффициентами)?

[Huobase]

Arigato,

a  = [[6, 12], [5, 2], [2, 10], [10, 100], [4, 12], [18, 9], [38, 152]]
a3 = [[6, 12], [5, 2], [2, 10], [10, 100], [4, 12], [18, 9], [38, 152]]
v = 20
a2 = []
sump = 0
a1 = [i[1] / i[0] for i in a]
while v > 0:
    m = max(a1)
    maxj = a1.index(m)
    if a[maxj][0] < v:
        sump += a1[maxj] * a[maxj][0]
        v -= a[maxj][0]
        a[maxj][0], a[maxj][1] = 0, 0
        a1[maxj] = 0
    else:
        sump += a1[maxj] * v
        a[maxj][0] = v
        v = 0
for k in range(len(a)):
    if a[k][0] == 0:
        a2.append(a3[k][0])
    elif a[k][0] != a3[k][0]:
        a2.append(a[k][0])
    else:
        a2.append(0)
print(a2)
print(sump)

Вот что получилось, но мне было бы интересно узнать, как можно упростить, или по-другому решить задачу

BDA, V это не ответ это максимальный объем который можно использовать, если интересно можете посмотреть тот код который я выше написал

[BDA]

Вот теперь стало понятно. Похоже, это задача о рюкзаке в чуть другой формулировке. А вы реализовали жадный алгоритм, который дает приближенное решение. По вашему коду: если будет дан объем больше суммы всех объемов, то код зациклится; мне кажется, что "обрезать" последний объем неверно. Если просто упрощать ваш код, то сразу бы отсортировал, а потом суммировал:

a  = [[6, 12], [5, 2], [2, 10], [10, 100], [4, 12], [18, 9], [38, 152]]
v = 20

a2 = [0] * len(a)
sump = 0

for k, v1, k1, i in sorted([(i[1] / i[0], i[0], i[1], j) for j, i in enumerate(a)], reverse = True):
    if v1 <= v:
        sump += k1
        a2[i] = v1
        v -= v1
    else:
        sump += k * v
        a2[i] = v
        break

print(a2)
print(sump)

[Huobase]

BDA, Спасибо за помощь, я думал о том как от цикла избавиться, но не получалось, теперь, посмотрев на ваш код, стало намного понятнее.