Школьная задачка, помогите пожалуйста!!!

[seppenen]

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

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

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

[VAL]

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

[gris]

Это не так сложно. Надо набрать близко к сумме, а потом приближаться, убирая одни предметы и набирая другие. Я набрал 21 штуку (6 позиций) на десятку ровно

[VAL]

gris в сообщении #766293 писал(а):

Это не так сложно. Надо набрать близко к сумме, а потом приближаться, убирая одни предметы и набирая другие. Я набрал 21 штуку (6 позиций) на десятку ровно

Думаю, проще и надежнее работать почти без подбора.
Я решал так: Число Фробениуса для цен двух самых дешевых товаров $F(13,32)=13\cdot32-13-32=321$. Значит, любая сумма бОльшая этого числа, набирается двумя данными товарами (подбором или простеньким линейным сравнением). Но $321$ значительно меньше, чем останется от тысячи центов после покупки остальных товаров.

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

[seppenen]

спасибо всем большое, вышло как то так

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