Алгоритм: набор суммы из множества других

[drronnie]

Господа, такая трабла: не могу придумать алгоритм....
Есть некоторое множество дробных чисел от меньше 1 до 1000. Мне нужно из них набрать целую сумму, например 2900.... но как найти подмножество чисел этого множества, которые в сумме дают то, что надо мне.... может кто сталкивался когда?

[onell]

от меньше 1 до 1000

- это значит от минус бесконечности? И по какому принципу должен происходить набор?

[vvs_adm]

Да нет, он наверняка хотел сказать - от 0 до 1000. Просто не смог.

[uhm]

Перебор всех вариантов?

[vvs_adm]

Перебор всех вариантов?

В инете есть алгоритмы вроде поприличнее. Только мне искать некогда, пусть автор сам ищет. Помнится задачки такие были, какие нужно иметь монеты, чтобы можно было составить любую сумму и т.д.

[alibek]

Да, выдача сдачи в разменных апаратах.
Или взвешивание.
Задача типичная, но я забыл, как называется.

[drronnie]

от меньше единицы это от меньше единицы.... например 0,37 грн.

Нужно из этого множества скоомбинировать заданную сумму.... ну например надо 4,50... мы выбираем 1,30; 1,20; 0,30; 0,70; 1 в сумме они дают на искомое число....

Алибек, а как она называется? То ли формулирую вопрос не правильно, но в поисковиках ничего похожего близко нет

[vvs_adm]

от меньше единицы это от меньше единицы.... например 0,37 грн.

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

[drronnie]

Ну однозначно отрицательные - это меньше нуля, а я говорил про меньше единицы. А вот вы видимо, vvs_adm, в школе искусство болтовни проходили, и освоили его на отлично: 3 ответа и ни одного по делу.

[vvs_adm]

Ну однозначно отрицательные - это меньше нуля, а я говорил про меньше единицы.

Прочитай еще раз то, что я написал. Можно три раза. И тогда ты поймешь...

3 ответа и ни одного по делу.

Ну вообще-то второй ответ - ну прямо таки в точку. А Alibek его дополнил, дальше некуда. Осталось только яндекс открыть... Или ты все-таки хочешь, что бы я за тебя поискал?

[drronnie]

vvs_adm, хорошо из трёх ответов два не в тему...
Я вот понять не могу, почему всегда на форумах возникают умники, которые сначала дают "исчерпывающие разъяснения", а потом советуют обратится к поисковикам... Ну не знаешь и не интересно - молчи; знаешь - скажи; не знаешь и ИНТЕРЕСНО - предложи вариант, давай дискутировать.... ИМХО
Лично я к помощи форумов обращаюсь только после долгих безрезултатных поисков, и такую цель, как отметиться в каждом топике не приследую.

А с монетками, кстати не совсем то. Там алгоритм выглядит так: берём наибольшую монетку, не превышающую искомую сумму, затем снова и так добираем монетки до тех пор, пока не набрали нужную сумму...

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

[vvs_adm]

Есть некоторое множество [положительных?] дробных чисел от [0?] меньше 1 до 1000

Ну вообще-то если бы ты корректно написал условие задачи, либо если бы onell не спросил, то и двух ответов "не в тему" просто бы не было. Хотя кто знает, может в твоей задаче дробные числа могут быть отрицательными? Почему бы и нет...

[drronnie]

Есть некоторое множество [положительных?] дробных чисел от [0?] меньше 1 до 1000

Вот это вопрос по существу... Да, положительных от нуля (не включая) его... Здесь речь идёт о суммах накладных, поэтому они не могут быть отрицательными и нулевыми

Да нет, он наверняка хотел сказать - от 0 до 1000. Просто не смог.

А это не более чем подковырка....

[Oxygen]

Вот алгоритм, который дает Котов:
Имеются монеты c различными фиксированными номиналами, выраженными в копейках (например, 3 и 5 копеек) в достаточном количестве. Написать программу COINS.*, которая:

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

Входные данные: Входной файл COINS.DAT содержит в первой строке сумму S (0 < S < 1000000000), во второй строке - N - количество различных номиналов (0 < S < 20), а в следующих N строках - А1 ... АN - номиналы (в порядке возрастания), которые можно использовать (0 < A1 < A2 < ... < AN < 1000000000).

Выходные данные: Выходной файл COINS.SOL должен содержать в первой строке знак "+", если заданную сумму S можно представить, и знак "-", если нельзя. Если представленная сумма существует, то следующие N строк должны содержать количества монет каждого номинала, которые необходимы для представления суммы S с помощью минимального количества монет.

Примеры ввода и вывода

Представить 514 копеек с помощью монет номиналом в 3 и 5 копеек

COINS.DAT:
514
2
3
5

COINS.SOL:
+
3
101

Представить 27 копеек с помощью монет номиналом в 5 и 13 копеек

COINS.DAT:
27
2
5
13

COINS.SOL:
-

Решение g6_1026:
Для решения этой задачи нам понадобится знать, как находить НОД. Для этого надо прочитать Задачу #1019: Банки.
Итак, найдем НОД номиналов всех монет. Если необходимая сумма не делится на НОД нацело, то сразу выводим "-" (мы никак не можем набрать 5 рублей монетками в 2 и 4 рубля! Монеты в 4 рубля - моя идея.). Если же необходимая сумма делится на НОД без остатка, то придется действовать хитро:
Возьмем монету с наибольшим номиналом, возьмем наибольшее количество монет, так чтобы их сумма не превышала искомую сумму. Теперь посчитаем НОД оставшихся монет. Если остаток искомой суммы от тех денег, которые мы собрали, не делится на НОД, то уменьшим количество монет с наибольшим номиналом на 1 и снова проверим, делится ли остаток на НОД. Если делится - то переходим к следующей монете, если нет - то опять уменьшаем на 1 количество монет. Если в какой то момент количество монет стало отрицательным, то выводим "-" и выходим. Если вся сумма выразилась в определенном количестве монет разных номиналов, то выводим "+" и количество монет разного номинала (для хранения количества монет удобно организовать массив).


Была ещё где-то зачача, решенная Окуловым. Но, к сожалению, сейчас посмотреть не могу, т.к. нет ворда.

[drronnie]

Oxygen, интересный алгоритм...попробую прикрутить к нему ограниченное количество монет....спасибо

[Efiop]

drronnie
1. Пиши полное условие. В этом множестве могут числа повторяться или все разные? Потом, выводит все варианты или же нужно набрать необходимую сумму, используя наименьшее кол-во чисел?
2. На форумах "Алгоритмы" поищи, там точно есть.
Она чем-то похожа на задачу про "Рюкзак" и "Мешок картошки".

Вот про рюкзак.

[vvs_adm]

А это не более чем подковырка....

Ладно, возможно перестарался, за подковырку извиняюсь.

[drronnie]

Efiop, некоторые могут повторяться, некоторые только в одном экземпляре...
Надо набрать сумму... не обязательно с меньшим количеством чисел, просто её нужно набрать, один вариант, не обязательно все...

vvs_adm, мир