Задачка на динамическое программирование

# -*- coding: utf-8 -*-
"""ADTLUPG.ipynb
 
Automatically generated by Colaboratory.
 
Original file is located at
    https://colab.research.google.com/drive/1AyNIrrOe2liMYQY1bAs8V0wEQNh8jmMt
"""
 
import pandas as pd
import numpy as np
 
control = 0.1458
df = pd.read_excel('/content/drive/MyDrive/Book_example.xls', header=3).iloc[:-1,:]
 
df['tmp'] = df.iloc[:, 0].str.split(',')
df['tmp'] = df['tmp'].map(set)
 
df['cnt'] = df.iloc[:, -3].cumsum()
ind = np.where(df['cnt'].values>control)[0][0]
adtlupg = set().union(*df.iloc[:ind, -2].to_list())
 
from itertools import combinations
 
res = []
flag = False
for i in range(1, len(adtlupgs)+1):
  for elem in combinations(adtlupgs, i):
    cnt = np.where((df['tmp'] - set(elem)).map(len) == 0, df.iloc[:, 2], 0).sum()
    if cnt >= control:
      res.append((set(elem), cnt))
      flag = True
      #print(set(elem, cnt))
      #break
  if flag:
    break
[print(*elem) for elem in res]
print(*max(res, key=lambda x: x[1]))

# -*- coding: utf-8 -*-
"""ADTLUPG.ipynb
 
Automatically generated by Colaboratory.
 
Original file is located at
    https://colab.research.google.com/drive/1AyNIrrOe2liMYQY1bAs8V0wEQNh8jmMt
"""
 
import pandas as pd
import numpy as np
 
control = 0.1458
df = pd.read_excel('/content/drive/MyDrive/Book_example.xls', header=3).iloc[:-1,:]
 
df['tmp'] = df.iloc[:, 0].str.split(',')
df['tmp'] = df['tmp'].map(set)
 
# отбираем комплекты с долей > 2% от control
ind = len(np.where(df.iloc[:,-2].values>control/50)[0])
adtlupgs = set().union(*df.iloc[:ind, -1])
# полный перебор
# adtlupgs = set().union(*df.iloc[:, -1])
 
from itertools import combinations
 
res = []
flag = False
for i in range(1, len(adtlupgs)+1):
  for elem in combinations(adtlupgs, i):
    cnt = np.where((df['tmp'] - set(elem)).map(len) == 0, df.iloc[:, 2], 0).sum()
    if cnt >= control:
      res.append((set(elem), cnt))
      flag = True
      #print(set(elem, cnt))
      #break
  if flag:
    break
[print(*elem) for elem in res]
print(*max(res, key=lambda x: x[1]))