деление монет (uva 562) - рекурсивное решение dp в python - PullRequest
Новая
       42

деление монет (uva 562) - рекурсивное решение dp в python

0 голосов
/ 18 июня 2020

Решаю эту задачу Разделение монет от увы. Задача является разновидностью хорошо известной задачи о ранце 0/1. Я пытаюсь немного подправить свою реализацию рюкзака 0/1, чтобы решить эту проблему. Я протестировал свой код с множеством тестовых примеров в автономном режиме, и он отлично работает, но когда я отправляю свой код, я получаю ошибку выполнения.

Когда я комментирую строки, в которых проверяю, найден ли результат подзадачи в словаре. Я получаю сообщение об ошибке превышения лимита времени.

Я не могу точно сказать, в чем проблема. Однако я чувствую, что запоминаю неправильные вещи.

Не могли бы вы взглянуть на мой код и попытаться помочь? Спасибо! 

def recSolve(vals, remW, allItm, idx, mem):

    if idx >= allItm or remW <= 0: # remW is the remaining amount the user could get (not exceeding total/2)
        return 0

    # check if it is in mem already
    if (remW, idx) in mem:
        return mem[(remW, idx)]

    # wight of the current item is more than the remaninig weight, skip to the next item
    if vals[idx] > remW:
        return recSolve(vals, remW, len(vals), idx+1, mem)
    else:
        # choose either picking the item or not (maximize the val)
        pickIt = recSolve(vals, remW - vals[idx], len(vals), idx+1, mem) + vals[idx]
        dontPickIt = recSolve(vals, remW, len(vals), idx+1, mem)
        res = max(pickIt, dontPickIt)
        mem[(remW, idx)] = res
        return res

def solve(vals, remW):
    mem = {}
    return recSolve(vals, remW, len(vals), 0, mem)

def takeInput():
    for i in range(int(input())):
        leng = input() # not used
        coins = input() 
        vals = [int(i) for i in coins.split(' ')] # the coins
        tot_w = sum(vals) 
        res= solve(vals, tot_w//2)  # maximizing the summation while not exceeding totalCoins/2
        print(tot_w - res - res) # getting the difference

takeInput()
...