Блог

 n = [5, 5, 4, 6] # number of list X = 8 # user have to pass 2 input has X, Y. Y = 8 result1 = [5] or [5] or [4] or [6] # if I choose 5. n = [5,4,6] # total = sum(result1). # total lt;= user X. result2 = [5] or [4] or [6] # total = sum(result2). # total lt;= user Y.  Ans : 2  n = [6,5,2,1,8]  X = 17 Y = 5 X = [8, 6, 2, 1]  Y = [5]  Ans: 5  n = [6,5,5,4,3]  X = 8  Y = 9 X = [5,3] # if I choose 5,3 remaining list of elements will be [6,5,4] Y = [5,4] Ans : 4  

1.Я не смог найти этот логический трюк. так что будьте добры, помогите мне. 2.Я попытался решить подобную сумму подмножеств. Но все равно я не мог понять логику. Примечание: используется язык python.

Если вы не ищете решение, которое максимизирует два значения, вы можете получить ближайшую сумму для каждого числа (удалив элементы первого результата из списка перед вторым поиском).

Если это так, вы можете подойти к нему рекурсивно, выбрав каждое число в качестве первого в комбинации и выполнив рекурсию с оставшимися числами, чтобы приблизиться к оставшейся сумме.

Чтобы обработать Y, вам понадобится вторая функция, которая удаляет (вычитает) результат X из вашего списка.

 def sumless(A,S):  if not S: return [] # target reached  closest = [] # track closest combo  for i,a in enumerate(A): # try each number as start of combo  if agt;S: continue # skip nnumbers that are too large  sl = [a]   sumless(A[i 1:],S-a) # find closest with rest  if sum(sl)gt;=sum(closest):   closest = sl # track closest combo  return closest   def subtract(A,B):  B = B.copy()  return [a for a in A if a not in B or B.pop(B.index(a))*0 ]  

Выход:

 n = [5,5,4,6]  X = 8 Y = 8 Xn = sumless(n,X) Yn = sumless(subtract(n,Xn),Y) print("X",Xn) # [6] print("Y",Yn) # [5]  n = [6,5,2,1,8]  X = 17 Y = 5 Xn = sumless(n,X) Yn = sumless(subtract(n,Xn),Y) print(Xn) # [6,2,1,8] print(Yn) # [5]  n = [6,5,5,4,3]  X = 8  Y = 9 Xn = sumless(n,X) Yn = sumless(subtract(n,Xn),Y) print(Xn) # [5,3] print(Yn) # [5,4]  

Если вам действительно нужно получить максимально возможные «ближайшие» суммы, вам нужно будет объединить все подмножества двух целевых объектов и найти лучшую пару подмножеств (т. Е. Где общая сумма наибольшая).:

 def sumGen(A,S): # sum set generator  if not S: return # target reached  for i,a in enumerate(A): # try each number as start   if agt;S: continue # skip if too large  yield [a] # return single value  for sl in sumGen(A[i 1:],S-a): # combine rest  yield [a] sl # return longer combos  def twoSums(A,X,Y):  bestX,bestY,bestSum = [],[],0 # track closest pair of combos  for Xn in sumGen(A,X): # subsets lt;= X  for Yn in sumGen(subtract(A,Xn),Y): # subsets lt;= Y (from rest)  if sum(Xn) sum(Yn)gt;bestSum: # track closest  bestX,bestY,bestSum = Xn,Yn,sum(Xn) sum(Yn)  return bestX,bestY  

Вывод: (то же, что и выше, учитывая, что в ваших примерах не подчеркивается различие между наивным поиском и оптимизированным)

 n = [5,5,4,6]  X = 8 Y = 8 print(*twoSums(n,X,Y)) # [6],[5]   n = [6,5,2,1,8]  X = 17 Y = 5 print(*twoSums(n,X,Y)) # [6, 2, 1, 8] [5]  n = [6,5,5,4,3]  X = 8  Y = 9 print(*twoSums(n,X,Y)) # [5, 3] [5, 4]  

Однако это имело бы значение:

 n = [6,5,5,4,3,2]  X = 9  Y = 15 Xn = sumless(n,X) Yn = sumless(subtract(n,Xn),Y) print(Xn) # [4,3,2] = 9 print(Yn) # [6,5] = 11 print(*twoSums(n,X,Y)) # [6, 3] [5, 5, 4] = 9, 14