Проверка кратности суммы

Здравствуйте, не могу понять, в какую сторону копать.

Дано.
===
1. Список товара, каждый товар характеризуется ценой за единицу товара и заданным количеством. Цена и к-во известны для каждого типа товара. Список товара конечен.
Цена и к-во - вещественные числа, ограничены двумя знаками после запятой.

2. Проверяемая сумма.

Задача
===
1. Определить, можно ли набрать проверяемую сумму из этого списка товара.
2. Если нельзя, то подобрать ближайшую возможную, но большую проверяемой.

Задача рюкзака вроде не подходит.
Может быть, подскажете, в каком направлении искать?

То есть каждый товар может быть взят в любом количестве от нуля до имеющегося? и тоже с "двумя знаками после запятой"?

Цитата vayer @ 21.11.14, 03:27

Задача рюкзака вроде не подходит.

Вполне себе подходит. Просто счётной единицей является не наличествующий товар, а его минимальная единица. Т.е. одна позиция в списке - это дохреналион предметов для упаковки.

Цитата Akina @ 21.11.14, 05:50

То есть каждый товар может быть взят в любом количестве от нуля до имеющегося? и тоже с "двумя знаками после запятой"?

Да, от 0 до заданного, с двумя знаками после запятой.

А какая тогда вариация "рюкзака"?

Сообщение отредактировано: vayer - 21.11.14, 07:08

Обычный рюкзак, без весовых коэффициентов.

Скажем, если у тебя 1,5 кг гвоздей, то в решении это 150 грузов по 0,01 кг.

Сообщение отредактировано: Akina - 21.11.14, 07:20

Блин, не понимаю, как адаптировать "рюкзак" на мой случай, можете разжевать дуболому?

Например,
товар1 цена1=100 к-во1=3
товар2 цена2=10 к-во2=0.5
товар3 цена3=25 к-во3=2
Проверяемая сумма - 230. Ее можно набрать: 100*2 + 25*1 + 10*0,5.
Если сумма 106, то ее не наберешь.

Рюкзак ведь только для целых чисел?

Может, здесь надо как-то искать возможные слагаемые (цены на товар) с коэффициентами (к-во товара)?

Цитата vayer @ 21.11.14, 08:19

Если сумма 106, то ее не наберешь.

Да запросто. Товар 1 в количестве 1,06.

Цитата vayer @ 21.11.14, 08:19

Рюкзак ведь только для целых чисел?

Нет. Для дискретных.

Добавлено 21.11.14, 08:31
Впрочем, если хочется работать с целыми, и у тебя единица учёта равна 0,01, просто умножь количества на 100, цены соответственно раздели. Просчитай. Затем выполни обратное преобразование.

Добавлено 21.11.14, 08:32
Задача - реальная или учебная?

Цитата Akina @ 21.11.14, 08:29

Задача - реальная

конечно, только вот щаз в магазине купил 1.36 буханки и 3.14 сосисок. подумал, 3 сосисок мало будет - не наемся.

Сообщение отредактировано: _lcf_ - 21.11.14, 08:37

Цитата Akina @ 21.11.14, 08:29

Да запросто. Товар 1 в количестве 1,06.

Нет, нельзя.

Видимо, я не до конца верно сформулировал задачу.

Цена идет за единицу (1) товара.

Пусть к-во будет всегда целое, к этому я могу преобразовать список, например:
товар1 цена1 = 100 к-во1 = 3 шт.
товар2 цена2 = 5 к-во2 = 1 шт.
товар3 цена3 = 25 к-во3 = 2 шт.

Товар не рассыпной, т.е. измеряется штуками, соответственно, к-во товара1 меняется от 1 до 3 с шагом 1.

А вот цена может быть с копейками.

Задача реальная: проверить сумму предоплаты на кратность стоимости и к-ву имеющегося в заказе товара. Если сумма некратна, то найти минимально возможную, но большую, чем проверяемая сумма, т.е. если сумму 106 руб. нельзя набрать, то ближайшая и большая будет - 125 = 100 * 1 + 25 * 1

Сообщение отредактировано: vayer - 21.11.14, 08:57

Цитата vayer @ 21.11.14, 08:51

цена может быть с копейками.

Т.е. в копейках она - целое. И количество - тоже целое.
Вот в этих единицах и работай.
И всё-таки

Цитата Akina @ 21.11.14, 08:29

Задача - реальная или учебная?

Задача реальная: проверить сумму предоплаты на кратность стоимости и к-ву имеющегося в заказе товара. Если сумма некратна, то найти минимально возможную, но большую, чем проверяемая сумма, т.е. если сумму 106 руб. нельзя набрать, то ближайшая и большая будет - 125 = 100 * 1 + 25 * 1

Жаль... а то Экселевский солвер щёлкает такие задачки как орехи...
Ну в общем программируй рюкзак и не парься.
Прикреплённый файл__________1.zip (3,92 Кбайт, скачиваний: 130)

Сообщение отредактировано: Akina - 21.11.14, 09:08

Цитата Akina @ 21.11.14, 08:53

Т.е. в копейках она - целое.

Не понял эту фразу, как целое, если с копейками?

Цена- целое число в копейках.

Непонятно, как терминологию рюкзака привязать к моей задаче.

Что будет весом и ценностью предметов для моей задачи?
Что есть максимальная ценность рюкзака для моей задачи? Ее же вроде мне искать не нужно, тогда что с ней делать?
Вместимость рюкзака - это куда прицепить?

====

Получается у меня есть рюкзак уже известной ценности и вместимости.
Надо найти, какими предметами можно заполнить рюкзак до заданной ценности и вместимости?

Сообщение отредактировано: vayer - 21.11.14, 09:28

Цитата vayer @ 21.11.14, 09:16

Что будет весом и ценностью предметов для моей задачи?

Вес - это твоя стоимость единицы товара в копейках.
Ценность всех предметов - единичная.
Вместимость рюкзака - это имеющаяся сумма.
Решать надо с минимальным переполнением. В оптимуме - с нулевым.
То есть на самом деле это не рюкзак, а одномерное заполнение с переполнением.