2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Школьная задачка, помогите пожалуйста!!!
Сообщение21.09.2013, 17:51 
Кате подарили на день рожденья подарочную карту на 10 евро. Сможешь ли ты выбрать себе сладости точно на сумму 10 евро? Купить нужно не менее 6 различных вещей.

мороженое - 51с
сок - 32с
шоколад - 1евро 15с
лимонад - 77с
леденец - 13с
чипсы - 1евро 53с
жевачка - 45с
батончик - 38с

Может у кого получиться. У меня выходит 10.10 евро

 
 
 
 Re: Школьная задачка, помогите пожалуйста!!!
Сообщение21.09.2013, 18:40 
Подбирается (разными способами и без проблем).
Например, возьмем всех товаров, кроме двух самых дешевых, по одному.
Остается купить на $1000-51-115-77-153-45-38=521$ центов леденцов и батончиков. Это легко сделать, купив, например, 13 леденцов и 11 батончиков.

 
 
 
 Re: Школьная задачка, помогите пожалуйста!!!
Сообщение21.09.2013, 18:49 
Аватара пользователя
Это не так сложно. Надо набрать близко к сумме, а потом приближаться, убирая одни предметы и набирая другие. Я набрал 21 штуку (6 позиций) на десятку ровно :oops:

 
 
 
 Re: Школьная задачка, помогите пожалуйста!!!
Сообщение21.09.2013, 19:06 
gris в сообщении #766293 писал(а):
Это не так сложно. Надо набрать близко к сумме, а потом приближаться, убирая одни предметы и набирая другие. Я набрал 21 штуку (6 позиций) на десятку ровно :oops:
Думаю, проще и надежнее работать почти без подбора.
Я решал так: Число Фробениуса для цен двух самых дешевых товаров $F(13,32)=13\cdot32-13-32=321$. Значит, любая сумма бОльшая этого числа, набирается двумя данными товарами (подбором или простеньким линейным сравнением). Но $321$ значительно меньше, чем останется от тысячи центов после покупки остальных товаров.

PS: Тем, кто не знает, что такое число Фробениуса, гуглите "coin problem". Для двух номиналов монет там все прозрачно. Для большего числа все сложнее. Но в данной задачи формулы для двух хватает с лихвой.

 
 
 
 Re: Школьная задачка, помогите пожалуйста!!!
Сообщение21.09.2013, 20:09 
спасибо всем большое, вышло как то так

2 сока = 64с
2 шоколада = 230с
6 лимонадов = 462с
6 леденцов = 78с
2 жевачки = 90с
2 батончика = 76с
-------------------
Итого: 1000с = 10 евро

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group