Как подогнать результат имея список цифр и итоговую сумму?
Есть список из какого-то числа цифр.
Например:
[1, 2, 7, 9]
И есть итоговая сумма, которая должна получится.
Например, итоговая сумма 51.
Цель: задействовать максимально возможное кол-во цифр из списка
и перемножить максимально возможное кол-во цифр.
Примерно вот так:
1*2 + 2*4 + 7*2 + 9*3 = 51
Как сделать так, чтобы 1*2 + 2*4 + 7*2 + 9*3 выдала программа?
На вход получила список из цифр и итоговую сумму, которую надо получить.
А выдала назад выражение.
Mrrl: Сумма всегда будет больше, чем любой элемент из списка. Но список "цифр" заранее неизвестен. Неизвестно какие цифры будут в списке. Так же заранее неизвестно их кол-во.
pcdesign: Если нет, то сформулируйте условие корректнее - что надо оптимизировать? Что значит "перемножить максимально возможное кол-во цифр"? У вас цифры умножаются на какие-то числа не из заданного набора. Какова роль этих чисел? Как они учитываются в оценке варианта решения?
Mrrl: Найти самое маленькое число и умножить на максимум не годится. Эта хитрая штуковина нужна для тётенек-бухгалтерш.
У них есть итоговая сумма.
Им надо сгенерить исходя из их стоимости товаров, которые у них есть в базе некую накладную.
Вот картинка накладной: fonclub-blog.ru/wp-content/uploads/2012/08/naklad.png
Из нее мы знаем итоговую сумму.
И у нас есть список цен на товары.
Надо подогнать все остальное.
pcdesign: То есть, на входе не цифры, а числа. И нужно найти вариант с более-менее одинаковыми коэффициентами при числах.
Делаете так. Заводите битовый массив B длиной, равной итоговой сумме, выраженной в общем делителе всех стоимостей товаров (например, в копейках - тогда можно справиться со счётом до 100 млн рублей, надеюсь, что этого хватит). Вычитаете из итоговой суммы S сумму стоимостей всех товаров (будем играть оптимистично - считать, что можем задействовать всё), результат назовём K. Сортируем товары от большей стоимости к меньшей (постараемся задействовать побольше дорогих товаров). Дальше делаем так:
B[0]=true;
foreach(int cost in Costs){
for(int a=cost;a <= S;a++) B[a]|=B[a-cost];
if(B[K]) break;
}
Если после этого цикла B[K]==true, то решение существует, и надо только понять, как оно получилось. Возможно, для этого понадобится дополнительный массив обратных ссылок.
Если нет, то делаете так:
foreach(int cost in Costs){
K+=cost;
if(B[K]) break;
}
Это мы разрешаем товарам, начиная с самого дорогого, не участвовать в наборе. Если в итоге получилось B[S]==false, значит, задача неразрешима.
Думаю, что строк в 30 программа уложится.
