Задача "Нет Монет"
Гоша готовится к выпускной дискотеке, и хочет купить одежды.Он скопил капитал в виде N монет. В магазине есть на продажу k предметов одежды со стоимостями O1, O2... Ok.
У кассира есть L монет стоимостями L1, L2,L3,L4... Гоша хочет купить максимальное количество вещей, так чтобы иметь возможность за них заплатить и получить точную сдачу при необходимости.Программа должна выдавать стоимость такой покупки при заданных условиях.
Вход три несортированных списка в таком порядке:
1. Монеты Гоши,
2. Монеты Кассира
3. Стоимость Одежды
Списки в квадратных скобках ([]), числа в списках и сами списки отделены запятой
У Гоши и Кассира от 5 до 10 монет номиналами от 7 до 100.
Товаров от 5 до 20 стоимость от 20 до 100
Обратите внимание на ограничение по времени (ограничений по количеству попыток нет).
P.S. При разных вариантов купить одно и тоже количество вещей необходимо выбрать вариант наименьший по стоимости.
Sample Input:
[7, 9, 9, 8, 7],[7, 8, 9, 8, 9],[8, 8, 6, 2, 4, 3]
Sample Output:
31
ЗАПИСАТЬ В коде и указать язык
Ответы
Ответ:
import itertools
import re
# t = '[1, 2, 5, 9, 4],[1, 2, 3, 4, 5],[8, 8, 6, 2, 4, 3]'
A = input('>> ')[1:-1].split('],[')
# A = t[1:-1].split('],[')
gosha_money = [int(item) for item in re.compile('\d+').findall(A[0])]
gosha_money.sort()
kassir_money = [int(item) for item in re.compile('\d+').findall(A[1])]
kassir_money.sort()
cost_cloths = [int(item) for item in re.compile('\d+').findall(A[2])]
cost_cloths.sort()
def sums(lis):
tmp = []
for L in range(0, len(lis)+1):
for subset in itertools.combinations(lis, L):
tmp.append(sum(subset))
return tmp
sum_g_m = sums(gosha_money)
sum_c_c = sums(cost_cloths)
sum_k_m = sums(kassir_money)
sum_g_m.sort(reverse=True)
sum_c_c.sort(reverse=True)
def main():
def check(check_var):
if item in sum_k_m:
return True
else:
return False
check_var = 0
for item in sum_g_m:
for item_2 in sum_c_c:
if item - item_2 > 0:
check_var = item - item_2
if check(check_var) == True:
return item_2
break
print(main())
Объяснение:
Python 3.
Запускаешь. Вставляешь строчку "[7, 9, 9, 8, 7],[7, 8, 9, 8, 9],[8, 8, 6, 2, 4, 3]" без кавычек и смотришь на результат.