Знаю, название туповатое и не отражает суть проблемы  Можно будет переименовать позже...

Итак проблема: Существуют N кучек чисел. Можно составлять комбинации, беря по числу из каждой кучки. Вес каждой комбинации  - банальная сумма содержащихся чисел. 


Необходим алгоритм, с помощью которого комбинации можно доставать начиная с самого большого веса и по убыванию. 

пример с N=3:

Кучка1: 10,5
Кучка2: 9,3
Кучка3: 10,5

соответственно комбинации и их порядок на выходе:

1) 10+9+10=29
2) 10+9+5=24
3) 10+9+5=24
4) 10+3+10=23
5) 5+9+5=19
6) 10+3+5=18
7) 10+3+5=18
8) 5+3+5=13

Решение влоб - создать всевозможные комбинации и рассортировать их. Решение не подходит, так как комбинаций может быть очень много.

А каков порядок этого "очень много"?

Порядок не определён. Ни количество в кучке, ни количество самих кучек. Может быть сколько угодно.

Добавлено через 40 секунд
Допустим 1 мио в каждой кучке и таких кучек 20.

прикольная задачка
общего решения, чтобы порядок сложности перехода к каждому элементу был вменяемым, в голову не пришло
однако появилась такая мысль:
если на самом деле интересны не все сочетания, а, например, первые M штук, то можно попробовать уменьшить сложность их получения
можно доказать, что первые M сочетаний используют только первые M элементов из каждой кучки (ну уж кучки отсортировать придётся)
так что алгоритм такой:
сначала берём по первому элементу из каждой кучки - это наш первый ответ
а на каждом следующем шаге K добавляем в какой-нибудь контейнер S все сочетания, содержащие хотя бы один элемент с номером K, а остальные элементы с номерами не больше K
потом выбираем наибольший, удаляем его из контейнера и возвращаем, как ответ

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

иллюстрация:
кучка1: 9,8,7,6,5,...
кучка2: 7,5,4,2,...
кучка3: 4,3,2,1,...

K=1:
  S<<9+7+4 //=20
  S={20}
  S>>20 (он же максимальный)
  S={}
  return 20;
K=2:
  S<<8+7+4 //=19
  S<<8+7+3 //=18
  S<<8+5+4 //=17
  S<<8+5+3 //=16
  S<<9+5+4 //=18
  S<<9+5+3 //=17
  S<<9+7+3 //=19
  S={19,19,18,18,17,17,16}
  S>>19
  S={19,18,18,17,17,16}
  return 19;
...

Добавлено через 2 минуты и 57 секунд
а вообще, можно попробовать поиспользовать какую-нибудь дополнительную информацию о числах в кучках (например, что в одной кучке числа будут значительно меньше/больше чисел в других кучках)

Это сообщение отредактировал(а) maxim1000 - 18.12.2008, 22:47