Участник:Gmorgachev/Копейка рубль бережет

Материал из DISCOPAL
Перейти к: навигация, поиск

Динамическое программирование для задачи о рюкзаке/Задачи/Копейка рубль бережет


Предполагаем, что на каждый товар можно сделать сколько угодно кратную скидку

class item:
    def __init__(self, name, cost, number):
        self.name = name
        self.cost = cost
        self.number = number
        self.sale_on_each = 0
 
def pen_rub_protect(T):
    total_sum = 0.
    for item in T:
        total_sum += item.cost * item.number
 
    delta = total_sum%1
    for i in T:
        # максимально возможная скидка на этот товар
        cur_sale = i.cost%1 * i.number
        if cur_sale >= delta:
            i.sale_on_each = delta / i.number
            return T
        i.sale_on_each = cur_sale / i.number
        delta -= cur_sale
 
    if delta > 0:
        return None
 
    return T


StasFomin (обсуждение) 10:04, 29 марта 2018 (MSK): Раз у вас питон, добавьте вызовов с тестами, чтобы я мог сразу позапускать готовый код.


import random
 
def sum_cost(T):
    sum_cost = 0
    for i in T:
        sum_cost += i.cost * i.number
 
    return sum_cost
 
def sum_cost_sale(T):
    sum_cost = 0
    for i in T:
        sum_cost += i.sale_on_each * i.number
 
    return sum_cost
 
 
total_test_num = random.randint(1, 10)
 
for j in range(total_test_num):
    test_num = random.randint(1, 100)
    T = []
    print("  number   ", "cost   ", "sale_on_each")
    for i in range(test_num):
        T.append(item(random.randint(100, 199),
                      random.randint(0, 80) + 0.01*random.randint(1, 99),
                      random.randint(1, 5)
                     ))
 
    pen_rub_protect(T)
    for i in T:
        print('% 8d' % i.number , '% 8.4f' % i.cost,  '% 4.4f' % i.sale_on_each)
    print('------------')
    print('result')
    print('------------')
    print(round(sum_cost(T), 7), round(sum_cost_sale(T), 7))
    print('------------')
    print('------------')


Измененный тест


StasFomin (обсуждение) 20:18, 25 апреля 2018 (MSK):

NameError: name 'item' is not defined

?



Оба фрагмента кода выше нужно запустить, там сначала решение, затем тесты.

Вот целиком (только что проверил, все работает):

import random
 
 
class item:
    def __init__(self, name, cost, number):
        self.name = name
        self.cost = cost
        self.number = number
        self.sale_on_each = 0
 
def pen_rub_protect(T):
    total_sum = 0.
    for item in T:
        total_sum += item.cost * item.number
 
    delta = total_sum%1
    for i in T:
        # максимально возможная скидка на этот товар
        cur_sale = i.cost%1 * i.number
        if cur_sale >= delta:
            i.sale_on_each = delta / i.number
            return T
        i.sale_on_each = cur_sale / i.number
        delta -= cur_sale
 
    if delta > 0:
        return None
 
    return T
 
def sum_cost(T):
    sum_cost = 0
    for i in T:
        sum_cost += i.cost * i.number
 
    return sum_cost
 
def sum_cost_sale(T):
    sum_cost = 0
    for i in T:
        sum_cost += i.sale_on_each * i.number
 
    return sum_cost
 
 
total_test_num = random.randint(1, 10)
 
for j in range(total_test_num):
    test_num = random.randint(1, 100)
    T = []
    print("  number   ", "cost   ", "sale_on_each")
    for i in range(test_num):
        T.append(item(random.randint(100, 199),
                      random.randint(0, 80) + 0.01*random.randint(1, 99),
                      random.randint(1, 5)
                     ))
 
    pen_rub_protect(T)
    for i in T:
        print('% 8d' % i.number , '% 8.4f' % i.cost,  '% 4.4f' % i.sale_on_each)
    print('------------')
    print('result')
    print('------------')
    print(round(sum_cost(T), 7), round(sum_cost_sale(T), 7))
    print('------------')
    print('------------')

StasFomin (обсуждение) 18:36, 8 мая 2018 (MSK): Нельзя давать скидку в нецелое число копеек. («i.sale_on_each = delta / i.number») Тут не получится ничего жадно-тупо, тут должно появится динамическое программирование.