英文:
0/1 Knapsack Problem with Dynamic Programming
问题
以下是已翻译的内容:
这是我尝试解决此线程中提出的问题。当我尝试以输入egg_weights = (1,5,10,25)
和n = 99
来运行它时,它似乎陷入了无限循环。对于较小的n
,该代码似乎能够给出正确的答案,尽管速度非常慢。这里出了什么问题?
以下是您提供的代码:
def dp_make_weight(egg_weights, target_weight, memo = {}):
if target_weight < 0:
return float('inf')
elif target_weight == 0:
return 0
elif target_weight > 0:
try:
return memo[target_weight]
except:
memo[target_weight] = float('inf')
for weight in egg_weights:
result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
if result < memo[target_weight]:
memo[target_weight] = result + 1
return result + 1
这是为了测试提供的代码:
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()
英文:
This is my attempt at the problem asked in this thread. When I try to run it with input egg_weights = (1,5,10,25)
and n = 99
, it seems to run into an infinite loop. The code seems to give the correct answer for smaller n
, albeit very slowly. What went wrong here?
def dp_make_weight(egg_weights, target_weight, memo = {}):
if target_weight < 0:
return float('inf')
elif target_weight == 0:
return 0
elif target_weight > 0:
try:
return memo[target_weight]
except:
memo[target_weight] = float('inf')
for weight in egg_weights:
result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
if result < memo[target_weight]:
memo[target_weight] = result + 1
return result + 1
Here's the code that was provided for testing purpose.
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()
答案1
得分: 1
如果您计划为不同的鸡蛋重量列表调用 dp_make_weight
,那么默认的 memo 参数应该按以下方式处理。还请阅读我在代码中的注释:
def dp_make_weight(egg_weights, target_weight, memo=None):
if memo is None:
memo = {}
infinity = float('inf')
if target_weight < 0:
return float('inf')
elif target_weight == 0:
return 0
else: # target_weight must be > 0
if target_weight in memo:
return memo[target_weight]
result = infinity
for weight in egg_weights:
# Only update result when dp_make_weight returns a value smaller than
# the current result value. Also note that the current value of memo
# is what is being passed and not a new, empty dict:
new_result = dp_make_weight(egg_weights, target_weight - weight, memo)
if new_result < result:
result = new_result
result += 1
memo[target_weight] = result
return result
if __name__ == '__main__':
egg_weights = (1, 5, 10, 25)
n = 99
print("Egg weights =", egg_weights)
print("n =", n)
print("Expected output: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
print("Actual output:", dp_make_weight(egg_weights, n))
print()
egg_weights = (1, 6, 9, 12, 13, 15)
n = 724
print("Egg weights =", egg_weights)
print("n =", n)
print("Expected output: 49")
print("Actual output:", dp_make_weight(egg_weights, n))
输出:
Egg weights = (1, 5, 10, 25)
n = 99
Expected output: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
Actual output: 9
Egg weights = (1, 6, 9, 12, 13, 15)
n = 724
Expected output: 49
Actual output: 49
英文:
If you are planning to call dp_make_weight
for different egg weight lists, then the default memo argument should be handled as follows. Also, read my comments in the code:
def dp_make_weight(egg_weights, target_weight, memo=None):
if memo is None:
memo = {}
infinity = float('inf')
if target_weight < 0:
return float('inf')
elif target_weight == 0:
return 0
else: # target_weight must be > 0
if target_weight in memo:
return memo[target_weight]
result = infinity
for weight in egg_weights:
# Only update result when dp_make_weight returns a value smaller than
# the current result value. Also note that the current value of memo
# is what is being passed and not a new, empty dict:
new_result = dp_make_weight(egg_weights, target_weight - weight, memo)
if new_result < result:
result = new_result
result += 1
memo[target_weight] = result
return result
if __name__ == '__main__':
egg_weights = (1, 5, 10, 25)
n = 99
print("Egg weights =", egg_weights)
print("n =", n)
print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
print("Actual output:", dp_make_weight(egg_weights, n))
print()
egg_weights = (1, 6, 9, 12, 13, 15)
n = 724
print("Egg weights =", egg_weights)
print("n =", n)
print("Expected ouput: 49")
print("Actual output:", dp_make_weight(egg_weights, n))
Prints:
Egg weights = (1, 5, 10, 25)
n = 99
Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
Actual output: 9
Egg weights = (1, 6, 9, 12, 13, 15)
n = 724
Expected ouput: 49
Actual output: 49
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论