Создать несколько комбинаций суммируя до 100

Question

Я хотел бы иметь возможность создавать несколько комбинаций, которые составляют до 100%, учитывая определенное количество «сегментов» с определенным «разностным коэффициентом». В приведенном ниже примере для упрощения разница в 20 раз, но я, вероятно, уменьшу ее до 1 в конечном решении.

Например, с 3 "ведрами" A, B, C вы можете получить:

A     100     80      80      60      60  ...   0
B     0       20      0       20      40  ...   0
C     0       0       20      20      0   ...   100

Каждый столбец - это одна комбинация (сумма 100), которую я хотел бы сохранить и провести дальнейшие вычисления.

Это бизнес-проблема, а не домашняя работа.

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

Очень ценится. Надеюсь, я объяснил достаточно ясно.

Answer 1

Эта проблема известна как разделов , а не комбинаций, что является чем-то другим.

Прежде всего: «разностный коэффициент» просто превращает проблему из поиска разделов в 100 в (в вашем примере) в поиск разделов из 5 (затем умножение на 20).

Далее: если количество сегментов постоянно, вы можете просто сделать (псевдокод):

for i = 0 to n
  for j = 0 to n-i
    output (i, j, n-(i+j))

Если количество сегментов будет динамическим, вам нужно быть немного умнее, но этот подход в основном будет работать.

Answer 2

Похоже, что это хорошо подойдет для кеширования и динамического программирования.

fun partition (partitions_left, value):
  if partitions_left == 0
    return empty_list

  if value == 0:
    return list of list of partitions_left 0 elements

  return_value = empty_list
  for possible_value from value downto 1:
    remainder = value-possible_value
    children = partition(partitions_left-1, remainder)
    for child in children:
     append (cons of possible_value and child) to return_value

  return return_value

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

Answer 3

Алгоритм, при котором вы можете составить список всех чисел от 0 до 100 с шагом 20 в списке A, а затем сделать копию списка A для списка B.

Далее сравните каждый списокЗначения A для списка B, видя, какие значения добавляют до 100 или менее, и сохраняют их записи в списке C. Затем, сделайте то же самое, чтобы снова отобразить список C (проверяя все значения между 0 и 100 с шагом 20), чтобы увидетькакие значения составляют до 100.