Создавать комбинации строк и в соответствии с комбинацией вычислять что-то (Python)

Question

Допустим, у меня есть следующие элементы:

items = [["1", 2, 10], ["2", 2, 6], ["3", 4, 11], ["4", 2, 4], ["5", 3, 5]]

, где строка является просто непрерывным числом.Второе значение в списках описывает вес элемента, третье значение описывает значение конкретного элемента.

Я хочу создать все возможные комбинации этих элементов (от 1 до 1 + 2 + 5или 4 + 2 + 3 + 5 + 1), а затем для каждой комбинации рассчитайте вес комбинации.Так, например, что, например, в случае примера «элемент 1 + 2 + 5», общий вес будет 2 + 2 + 3 = 7. Это должно быть сделано для каждой комбинации.Кроме того, мне нужно рассчитать стоимость этих 3 предметов.Однако ограничение - это максимальный вес, скажем, х!

Пока у меня есть следующее:

from itertools import *

x5 = permutations("12345", 5)
x4 = permutations("12345", 4)
x3 = permutations("12345", 3)
x2 = permutations("12345", 2)
x1 = permutations("12345", 1)

x5 = list(x5)
x4 = list(x4)
x3 = list(x3)
x2 = list(x2)
x1 = list(x1)

x5.append(x4)
x5.append(x3)
x5.append(x2)
x5.append(x1)

combs = x5.

Это дает мне все комбинации ... но с этого момента я абсолютно невежественен.

Answer 1

Это даст вам все комбинации, их веса и их значения и позволит вам фильтровать по максимальному весу.

items = [["1", 2, 10], ["2", 2, 6], ["3", 4, 11], ["4", 2, 4], ["5", 3, 5]]

res = []
max_wt = 100
for i in range(len(items)):
    combo = []
    combo_wt = 0
    combo_val = 0
    for j in range(len(items)-i):
        combo+=items[i+j][0]
        combo_wt+=items[i+j][1]
        combo_val+=items[i+j][2]
        print(combo, combo_wt, combo_val)
        if (combo_wt < max_wt):
            arr=[]
            arr+=(combo, combo_wt, combo_val)
            res.append(arr)
print(res)

Обратите внимание, что в вашем коде есть перестановки, а не комбинации,хотя вы спрашиваете о комбинациях (что имеет наибольшее значение в такого рода проблемах; я думаю о том, что «я охотник за сокровищами и могу нести только такой большой вес. Какие предметы я должен взять, чтобы максимизировать свою прибыль?»проблемы)

Answer 2

То, что вам нужно, это комбинации, а не перестановки (перестановки данной комбинации дадут тот же общий вес)

Чтобы вычислить итоговые значения веса, будет легче создать словарь с вашимстроки в качестве ключа и соответствующие веса в качестве значения.

Тогда комбинация с общей структурой веса может быть легко построена с использованием словарного понимания.

Вот как вы можете это сделать:

from itertools import *

items = [["1", 2, 10], ["2", 2, 6], ["3", 4, 11], ["4", 2, 4], ["5", 3, 5]]

values  = [item[0] for item in items]
weights = {item[0]:item[1] for item in items}
combos  = []
for size in range(len(values)): combos += combinations(values,size+1)
comboWeights = { combo:sum([weights[value] for value in combo]) for combo in combos }

Результирующий словарь comboWeights имеет комбинации кортежей в качестве ключей и общие веса в качестве значений:

for combo,weight in comboWeights.items(): print(combo,weight)

('1',) 2
('2',) 2
('3',) 4
('4',) 2
('5',) 3
('1', '2') 4
('1', '3') 6
('1', '4') 4
('1', '5') 5
('2', '3') 6
('2', '4') 4
('2', '5') 5
('3', '4') 6
('3', '5') 7
('4', '5') 5
('1', '2', '3') 8
('1', '2', '4') 6
('1', '2', '5') 7
('1', '3', '4') 8
('1', '3', '5') 9
('1', '4', '5') 7
('2', '3', '4') 8
('2', '3', '5') 9
('2', '4', '5') 7
('3', '4', '5') 9
('1', '2', '3', '4') 10
('1', '2', '3', '5') 11
('1', '2', '4', '5') 9
('1', '3', '4', '5') 11
('2', '3', '4', '5') 11
('1', '2', '3', '4', '5') 13

Answer 3

Есть 2 ** (len(items)) - 1 комбинаций для изучения.Вы можете рассматривать это как битовый вектор и легко перебирать его:

items = [["1", 2, 10], ["2", 2, 6], ["3", 4, 11], ["4", 2, 4], ["5", 3, 5]]

for i in range(2**len(items) - 1):
    bitvec = bin(i)[2:]   # convert to string containing 0 and 1
    selected = [items[k] for k, b in enumerate(bitvec) if b=='1']
    # selected now contains a unique combination from items