Комбинаторная задача о мороженом

[kojemiaka]

Добрый день,

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

Мама купила три (n в общем случае) типа мороженого.

3 штуки 1-го типа по 40 рублей каждое
3 штуки 2-го типа по 30 рублей каждое
3 штуки 3-го типа по 10 рублей каждое


Итого всего мороженого куплено на 240 рублей. Допустим, что мы можем вернуться в магазин и попросить обменять наше мороженое на другое, не выходя за пределы начальной суммы и оставаясь как можно ближе к ней. Выбирать мы можем из всё тех же 3х типов мороженого.

Вопрос: какие комбинации разных типов мороженого мы можем получить?

Например, максимальное число мороженных, которое мы можем купить 24, т.к. 240/10=24. Минимальное число - купить самые дорогие, их получится 6 штук. Какие комбинации мы можем составить в промежутке?

Уже начав думать над алгоритмом, я подумал купить вначале самое дорогое мороженое на всю сумму, потом продавать по одной единице и смотреть, что можно купить затем. Таким образом получается некое дерево. Но проблема в том, что с определенной глубины листья начинают повторяться.

[Leu]

kojemiaka в сообщении #580156 писал(а):

Добрый день
Уже начав думать над алгоритмом, я подумал купить вначале самое дорогое мороженое на всю сумму, потом продавать по одной единице и смотреть, что можно купить затем. Таким образом получается некое дерево. Но проблема в том, что с определенной глубины листья начинают повторяться.

добрый вечер)

поскольку данная задача на комбинаторику разбиений, то вообщем, не существенно, сколько и какого мороженного мама купила в самом начале. Главное знать сумму - 240 р.
Для дальнейшего решения переформулируем задачу в более удобный вид:
Сколькими способами можно потратить на мороженное 240 р., если в ассортименте имеется мороженое по цене 10, 30 и 40 р. за штуку?

[svv]

Можно ещё так:
Сколько решений в неотрицательных целых числах имеет уравнение $1a+3b+4c=24$ ?

[kojemiaka]

Leu в сообщении #582456 писал(а):

Сколькими способами можно потратить на мороженное 240 р., если в ассортименте имеется мороженое по цене 10, 30 и 40 р. за штуку?

Добрый вечер,

Да, но нас интересует не только количество способов, но и сами комбинации.

-- 09.06.2012, 03:50 --

svv в сообщении #582463 писал(а):

Можно ещё так:
Сколько решений в неотрицательных целых числах имеет уравнение $1a+3b+4c=24$ ?

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

Есть решение.
Во вложенных циклах увеличивать значения $a$, $b$ и $c$ последовательно, смотря на каждом шаге какое количесво самых дешёвых единиц мы можем купить на оставшиеся деньги.

for (int a=0; a<=aMax; a++){
     for (int b=0; b<=bMax; b ++){
          c = 24/1;
          cout << (a, b, c);
}
}

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

Но в этом алгоритме меня смущает то, что если типов мороженных n, то нужно делать n-1 вложенных циклов. А мы не знаем заранее сколько типов мороженого есть в магазине, в который сходила мама:).

[Профессор Снэйп]

svv в сообщении #582463 писал(а):

Можно ещё так:
Сколько решений в неотрицательных целых числах имеет уравнение $1a+3b+4c=24$ ?

В условии сказано

kojemiaka в сообщении #580156 писал(а):

не выходя за пределы начальной суммы

Так что правильно $1a+3b+4c \leqslant 24$

Правда, там ещё сказано

kojemiaka в сообщении #580156 писал(а):

оставаясь как можно ближе к ней.

Боюсь, что надо уточнять условие

[kojemiaka]

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

[Профессор Снэйп]

kojemiaka в сообщении #582477 писал(а):

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

Поскольку самое дешёвое стоит $10$ рублей, а два других $30$ рублей и $40$ рублей, то придётся поторатить все деньги. Зачем тогда эта ненужная приписка про "как можно ближе"?

[Leu]

kojemiaka в сообщении #582477 писал(а):

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

может, имеется ввиду, что допустим небольшой перерасход денег, их довложение в покупку мороженого?

kojemiaka в сообщении #582465 писал(а):

Добрый вечер,

Да, но нас интересует не только количество способов, но и сами комбинации.

доброе утро)
ну так это очевидно - сами комбинации мы получаем перебором!

Профессор Снэйп в сообщении #582480 писал(а):

Поскольку самое дешёвое стоит $10$ рублей, а два других $30$ рублей и $40$ рублей, то придётся поторатить все деньги

(Оффтоп)

предлагаю все деньги не тратить - на сэкономленные сходим в кино

[bot]

(Оффтоп)

Leu в сообщении #582491 писал(а):

предлагаю все деньги не тратить - на сэкономленные сходим в кино

Не имею понятия, сколько сейчас стоит сходить в кино, но мне кажется добавлять придётся много, возможно даже не к 10 рублям, а ко всей сумме.

[Профессор Снэйп]

(Оффтоп)

bot в сообщении #582493 писал(а):

Не имею понятия, сколько сейчас стоит сходить в кино

От 150 до 400. Хотя бывает и дороже 400.

Кинотеатры разные, есть навороченные, показывают фильмы в 4D формате. Я на таких сеансах ни разу не был. Смотрел "Аватар" в 3D, с очками, за 400 рублей.

[Leu]

(Оффтоп)

Профессор Снэйп в сообщении #582499 писал(а):

Кинотеатры разные, есть навороченные, показывают фильмы в 4D формате. Я на таких сеансах ни разу не был. Смотрел "Аватар" в 3D, с очками, за 400 рублей.

есть даже "7-D", "8-D", где под дополнительными размерностями они подразумевают дополнительные эффекты - брызги водой на зрителя, дым, запахи, движение кресел, шуршание чем-то под ногами и т.п.

kojemiaka в сообщении #580156 писал(а):

Мама купила три (n в общем случае) типа мороженого.

3 штуки 1-го типа по 40 рублей каждое
3 штуки 2-го типа по 30 рублей каждое
3 штуки 3-го типа по 10 рублей каждое

вообще, где вы видели, чтоб мама стока мороженого купила сразу?

[kojemiaka]

Профессор Снэйп в сообщении #582480 писал(а):

Поскольку самое дешёвое стоит $10$ рублей, а два других $30$ рублей и $40$ рублей, то придётся поторатить все деньги. Зачем тогда эта ненужная приписка про "как можно ближе"?

В общем случае суммы не круглые.

[Leu]

kojemiaka в сообщении #582613 писал(а):

В общем случае суммы не круглые.

тогда условие надо сформулировать корректнее

[kojemiaka]

В чем нужно уточнение?

[Leu]

в самом условии - если суммы не круглые, то требуется уложится строго в отведенную сумму, или можно перебрать/недобрать?