Долгое время я пользовался кредитной картой. Это действительно удобно, если соблюдать грейс период и не снимать наличные. Как гласит поговорка, «доллар сегодня стоит дороже, чем доллар завтра». Так зачем платить сегодня, если можно заплатить спустя месяц, а иногда и взять бесплатную рассрочку? Впрочем, от кредитки я уже отказался. Почему — выходит за рамки тематики этого блога.
Однако, пока пользовался, передо мной стояла задача компенсации покупок баллами «Браво». Для тех, кто не в курсе: за каждые 100 рублей покупок начисляется 1 балл. С помощью накопленных баллов спустя примерно месяц можно компенсировать покупки в некоторых категориях, чаще всего в ресторанах и кафе. Проблема в следующем: если у меня есть, например, 100 баллов и несколько покупок на разные суммы, то какие суммы выбрать для компенсации, чтобы использовать как можно большее количество баллов?
Чтобы справиться с этой проблемой, нужно применить алгоритм решения «задачи о рюкзаке» (задачи о ранце, knapsack problem). Имеем рюкзак и набор товаров, которые в него можно положить. Объём рюкзака ограничен. Товары имеют разный вес и разную стоимость. Как запихнуть в рюкзак наибольшее количество наиболее дорогих товаров? Но применительно к баллам «Браво» задача о рюкзаке вырождается в случай, когда вес «товара» равен его стоимости.
И… впервые попрошу помощи у читателей, если найдутся знатоки JavaScript / Google App Script. Я написал решение задачи на Python, но у меня никак не получается полностью перевести её в Таблицы Google, то есть на Google App Script.
Вот решение на Python:
# Ёмкость "рюкзака"
value = input("Введи кол-во баллов (формат — число, например: 1646)\n")
# Веса "товаров" = Цены "товаров" (частный случай "Задачи о рюкзаке")
weights = input("\nВведи покупки для коменсации\n(формат — числа через запятую,\nнапример: 899,469.75, 1040,1408,1048)\n")
def floor(n):
return int(n // 1)
W = int(value)
weights = weights.split(",")
w = [floor(float(x)) for x in weights]
def main(w, W):
print("\nВеса: %s\nВместимость: %d\n" % (w, W))
T={0:0} #Хэш: самая большая стоимость набора для веса — {вес:стоимость}
Solution={0:[]}
for i in range(0,len(w)):
T_old=dict(T)
#Цикл по всем полученным частичным суммам
for x in T_old:
if (x+w[i])<=W:
if ((x+w[i]) not in T) or (T[x+w[i]]<T_old[x]+w[i]):
T[x+w[i]]=T_old[x]+w[i]
Solution[x+w[i]]=Solution[x]+[i]
ResultCost = max(T.values())
Result = [w[s] for s in Solution[ResultCost]]
Result.sort(reverse=True)
print("Решение: %s\nСумма: %d\n" % (Result, ResultCost))
return (Result, ResultCost)
if __name__ == "__main__":
main(w, W)
Получаем ответ в таком виде:
Понятное дело, что работать с консолью — удовольствие так себе. Поэтому перед публикацией этой статьи я задумал перевести всё это дело в Таблицы. Просидел над этим три дня, и единственное, что получил — ответ в виде числа, равного сумме компенсации. Но никак не могу получить массив самих решений: сумм, которые нужно компенсировать. Сдаюсь. Поэтому ниже исходный код скрипта Google. Если кто-то может посоветовать, буду очень благодарен!
// Для теста хардкодим все исходные значения
W = 1646;
w = [899, 469.75, 1040, 1408, 1048];
W = Number(W);
// Округляем вниз все "веса", т.к. копейки при компенсации баллами не учитываются
w = w.map(Number);
w = w.map(Math.floor);
// Избавляемся от возникших при округлении нулей
w = w.filter(Number);
var v = w;
var n = w.length;
var T = {0:0}; // #Хэш: самая большая стоимость набора для веса — {вес:стоимость}
var Solution = {0:[]};
var T_old;
var tmp;
for (i=0; i<=n; i++) {
T_old = T;
for (x in T_old) {
x = parseInt(x);
if (x+w[i] <= W) {
if ( (getKeyByValue(T, x+w[i]) == -1) || (T[x+w[i]] < T_old[x]+w[i]) ) { T[x+w[i]] = T_old[x]+w[i]; tmp = Solution[x]; tmp.push(i); Solution[x+w[i]] = tmp; } } } } var arr = Object.values(T); var ResultCost = Math.max(...arr); var Result = []; for (s in Solution[ResultCost]) { Result.push(w[s]); } return([ResultCost, Result]); } function getKeyByValue(object, value) { //value = Number(value); var res = Object.keys(object).find(key => object[key] === value);
if(res) {
return(Number(res));
}else{
return(-1);
}
}
