时间戳

首页 > 解决方案 > 利用递归仅返回基本情况的优化问题（Python）

python - 利用递归仅返回基本情况的优化问题（Python）

问题描述

我正在处理的这段代码有问题。该问题在代码的文档字符串中进行了概述。我的函数不断返回递归算法的基本情况而不是最佳解决方案，但我不知道为什么。这是代码：

###########################
# 6.0002 Problem Set 1b: Space Change
# Name:
# Collaborators:
# Time:
# Author: charz, cdenise

#================================
# Part B: Golden Eggs
#================================

# Problem 1
def dp_make_weight(egg_weights, target_weight, memo = {}):
    """
    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is
    an infinite supply of eggs of each weight, and there is always a egg of value 1.

    Parameters:
    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)
    target_weight - int, amount of weight we want to find eggs to fit
    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)

    Returns: int, smallest number of eggs needed to make target weight
    """
    # TODO: Your code here
    #sort eggs by biggest to smallest
    egg_weights = sorted(egg_weights,reverse=True)
    #base case
    if target_weight == 0 or egg_weights == []:
        num_eggs = 0


    #start by taking the biggest egg, if you cant go right (move on)
    elif target_weight - egg_weights[0] < 0:
        num_eggs = dp_make_weight(egg_weights[1:],target_weight)
    #if u can take the egg, take it
    else:
        num_eggs = dp_make_weight(egg_weights,target_weight-egg_weights[0])
    return num_eggs






# EXAMPLE TESTING CODE, feel free to add more if you'd like
if __name__ == '__main__':
    egg_weights = (1,5,10,25)
    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

#what i am getting 
# Egg weights = (1, 5, 10, 25)
# n = 99
# Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
# Actual output: 0

标签： pythonrecursionoptimization

解决方案

问题是当你取一个鸡蛋时，你并没有增加鸡蛋的数量。

要修复替换：

num_eggs = dp_make_weight(egg_weights,target_weight-egg_weights[0])

和

num_eggs = 1 + dp_make_weight(egg_weights,target_weight-egg_weights[0])

推荐阅读