задача туриста

[Maximus_G]

Добрый день!
Возможно вопрос немного не в тему, но все же здесь умные люди, может кто подскажет.
Есть вот такие числа и их порядковый номер:

1 1000
2 3000
3 2200
4 1000
5 5000
6 300
7 250
8 1000
9 800
10 1400
11 2300

Есть интервал : 4176 - 3888

Задача такая: необходимо провести группировку вышеприведенных чисел таким образом, чтобы они попали в этот интервал. Количество может быть разное. Например: 1000(1) + 3000(2) = 4000 - в интервал попадает, больше никакого другого числа добавить нельзя, потому что выйдет из интервала. To-есть это Вариант 1. И так дальше:1000(4) + 2300(11) + 800(9) = 4100. Это Вариант 2. Ну и так дальше. Нужно понимать, что 1000 c 1го числа, и 1000 c 4го это разные варианты, поэтому 1000(1)+3000(2) и 1000(4)+3000(2) - это 2 разных варианта.

Может кто подбросит идейку какаю... алгоритм, так как буду писать это дело на вб.
Спасибо большое!

[Maximus_G]

Я так понял, задача сводится к простому.
Найти все возможные суммы для заданных чисел по 2, 3, 4 и так до 11 элементов, но число нельзя суммировать само c собой... Как же это сделать ?

Вот на другом форуме мне дали эту ссылку [url=http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004]http://rain.ifmo.ru/cat/view.php/theory/unsorted/approx-2004[/url], но я там ничего не понимаю... Может кто знающий посмотрит и подскажет ?

[Евгений Б.]

Source of the post
Я так понял, задача сводится к простому.
Найти все возможные суммы для заданных чисел по 2, 3, 4 и так до 11 элементов, но число нельзя суммировать само c собой... Как же это сделать ?

то есть нужно сгенерировать и вывести все возможные суммы?
если так, то это не сложно:
надо сгенерировать все подмножества данного множества и найти сумму элементов каждого полученного подмножества

[Maximus_G]

Source of the post
то есть нужно сгенерировать и вывести все возможные суммы?
если так, то это не сложно:
надо сгенерировать все подмножества данного множества и найти сумму элементов каждого полученного подмножества

Можна подробней ?

Может кто знает как вообще получают все значения сочетаний из n элементов. Формулу я знаю, тоесть можна узнать сколько их... a как узнать какие они ?

[Евгений Б.]

Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}

[Maximus_G]

Source of the post
Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}

Спасибо большое, буду читать