Задача о деньгах.

← →
Дмитрий С © (2012-06-07 17:13) [0]

Есть номиналы купюр: 10 50 100 500 1000 5000.
Известно количество купюр и их сумма.
Вопрос: можно ли зная количество купюр и сумму однозначно узнать сколько купюр каждого номинала?

Значения для примера:
Количество: 776
Сумма: 268360

← →
Юрий Зотов © (2012-06-07 17:19) [1]

Линейное программирование?

← →
БарЛог © (2012-06-07 17:19) [2]

> Есть номиналы купюр: 10 50 100 500 1000 5000.

Эт хорошо, когда есть :)

> Вопрос: можно ли зная количество купюр и сумму однозначно узнать сколько купюр каждого номинала?

нет конечно. было ж недавно. из фарша корову не сделаешь.

← →
БарЛог © (2012-06-07 17:21) [3]

Пардон, беру слова обратно. Про количество купюр не углядел :(

← →
Думкин_ (2012-06-07 17:23) [4]

> Вопрос: можно ли зная количество купюр и сумму однозначно
> узнать сколько купюр каждого номинала?

Сумма - 900. Купюр 9.

1*500 + 8*50=9*100

← →
Юрий Зотов © (2012-06-07 17:27) [5]

Да, не совсем линейное программирование. Условия экстремума не хватает.

← →
TUser © (2012-06-07 17:34) [6]

В данном случае - кажется, да. Но не при всех номиналах так. Например, 10+20=11+19. Возможно, необходимое и достаточное условие - никакие две разницы между номиналами не равны. Необходимость очевидна, достаточность, наверное, можно попробовать доказать

← →
tesseract © (2012-06-07 17:40) [7]

Это не из Кнута ли задачка? Что-то подобное было на олимпиаде, когда еще в лицее учился.

← →
TUser © (2012-06-07 17:43) [8]

> достаточность, наверное, можно попробовать доказать

но лучше не пробовать: 10+20+30=11+22+27

← →
Дмитрий С © (2012-06-07 17:46) [9]

> TUser © (07.06.12 17:34) [6]

Сомневаюсь, что достаточно. Вот если б номиналы, разделенные на их НОД, образовывали множество различных простых чисел, то даже количества купюр бы не требовалось знать:)

← →
Дмитрий С © (2012-06-07 17:49) [10]

Например 11 53 101 499 997 и 4999 рублей))

← →
Дмитрий С © (2012-06-07 17:51) [11]

Хотя нет и этого недостаточно:)

← →
han_malign (2012-06-07 17:51) [12]

> Условия экстремума не хватает.

- вводится искусственно - как раз для проверки единственности
- оптимизация по предпочтению больших/малых копюр(функция с весами отличными от исходных номиналов), ...

← →
AlexKniga (2012-06-07 23:32) [13]

Целочисленная математика лучшее, чтобы вштырило насухую.
Для примера:
http://physmatica.ru/Articles/Mathematics/Integer.htm

← →
Юрий Зотов © (2012-06-08 13:57) [14]

В [4] уже показано, что однозначного решения задача может и не иметь - в том виде, как она сформулирована в топике.

Но если, как сказано в [12] использовать дополнительное условие (скажем, предпочтительность крупных или мелких купюр), то получаем задачу линейного программирования, методы решения которой известны.

← →
MsGuns © (2012-06-08 14:27) [15]

>использовать дополнительное условие

Скажем, условие - "Минимальная зарплата Ю.Зотова за месяц в рублях" (бо в еврах и ам.тугриках номиналов таких нема)
и ремарка петитом внизу : "Юрий мелких денег не любит"

:)))

← →
Юрий Зотов © (2012-06-08 15:06) [16]

> MsGuns © (08.06.12 14:27) [15]

В данном случае дело не столько в качестве, сколько в количестве...
:o)

← →
MsGuns © (2012-06-08 15:10) [17]

Т.е. ты согласился бы взять 26 836 десяток ?

← →
Дмитрий С © (2012-06-08 15:41) [18]

> Т.е. ты согласился бы взять 26 836 десяток ?

А ты нет? :)

← →
Юрий Зотов © (2012-06-08 15:44) [19]

> MsGuns © (08.06.12 15:10) [17]
> Т.е. ты согласился бы взять 26 836 десяток ?

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

← →
Думкин_ (2012-06-08 16:01) [20]

> Т.е. ты согласился бы взять 26 836 десяток ?

Взял бы. Банк берет долю за пересчет в приеме такого, но нахалявуиуксуссладкий. Куда подходить?

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

>Куда подходить?

К Дмитрию эс

← →
Думкин_ (2012-06-08 16:04) [23]

> [19] Юрий Зотов © (08.06.12 15:44)
> > Т.е. ты согласился бы взять 26 836 десяток ?
>
> При наличии носильщика до ближайшего банка. Поскольку десятки
> в России железные, бумажных почти не осталось.

Это сколько ведер выйдет?

← →
Думкин_ (2012-06-08 16:07) [25]

> Inovet © (08.06.12 16:05) [24]

Богаты красноярские мужики - деньги ведрами считают. Мы по старинке, послюнявим и пальчиками их, пальчиками.

Скорее всего автор забыл дописать что должен применяться жадный алгоритм.

← →
Думкин_ (2012-06-08 16:11) [27]

> Богаты красноярские мужики - деньги ведрами считают.

Хотя вот говорят есть масковские иные, так те камазами. Только один сейчас коз разводит, а второй недавно откинулся и опять людишек надул на 3 буквы!! Ждем второй ходки.

> Думкин_ (08.06.2012 16:01:20) [20]

И ты тоже хочешь в долю к банку

← →
Думкин_ (2012-06-08 16:26) [29]

Задача о деньгах. Найти похожие ветки