0/1背包问题的动态规划解法

huangapple
go评论106阅读模式
英文:

0/1 Knapsack Problem with Dynamic Programming

问题

以下是已翻译的内容：

这是我尝试解决此线程中提出的问题。当我尝试以输入egg_weights = (1,5,10,25)和n = 99来运行它时，它似乎陷入了无限循环。对于较小的n，该代码似乎能够给出正确的答案，尽管速度非常慢。这里出了什么问题？

以下是您提供的代码：

  1. def dp_make_weight(egg_weights, target_weight, memo = {}):
  2.     if target_weight < 0:
  3.         return float('inf')
  4.     elif target_weight == 0:
  5.         return 0
  6.     elif target_weight > 0:
  7.         try:
  8.             return memo[target_weight]
  9.         except:
  10.             memo[target_weight] = float('inf')
  11.             for weight in egg_weights:
  12.                 result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
  13.                 if result < memo[target_weight]:
  14.                     memo[target_weight] = result + 1
  15.         return result + 1

这是为了测试提供的代码：

  1. if __name__ == '__main__':
  2.     egg_weights = (1, 5, 10, 25)
  3.     n = 99
  4.     print("Egg weights = (1, 5, 10, 25)")
  5.     print("n = 99")
  6.     print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
  7.     print("Actual output:", dp_make_weight(egg_weights, n))
  8.     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?

  1. def dp_make_weight(egg_weights, target_weight, memo = {}):
  2.     if target_weight < 0:
  3.         return float('inf')
  4.     elif target_weight == 0:
  5.         return 0
  6.     elif target_weight > 0:
  7.         try:
  8.             return memo[target_weight]
  9.         except:
  10.             memo[target_weight] = float('inf')
  11.             for weight in egg_weights:
  12.                 result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
  13.                 if result < memo[target_weight]:
  14.                     memo[target_weight] = result + 1
  15.         return result + 1

Here's the code that was provided for testing purpose.

  1. if __name__ == '__main__':
  2.     egg_weights = (1, 5, 10, 25)
  3.     n = 99
  4.     print("Egg weights = (1, 5, 10, 25)")
  5.     print("n = 99")
  6.     print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
  7.     print("Actual output:", dp_make_weight(egg_weights, n))
  8.     print()

答案1

得分: 1

如果您计划为不同的鸡蛋重量列表调用 dp_make_weight，那么默认的 memo 参数应该按以下方式处理。还请阅读我在代码中的注释：

  1. def dp_make_weight(egg_weights, target_weight, memo=None):
  2.     if memo is None:
  3.         memo = {}
  5.     infinity = float('inf')
  7.     if target_weight < 0:
  8.         return float('inf')
  9.     elif target_weight == 0:
  10.         return 0
  11.     else: # target_weight must be > 0
  12.         if target_weight in memo:
  13.             return memo[target_weight]
  14.         result = infinity
  15.         for weight in egg_weights:
  16.             # Only update result when dp_make_weight returns a value smaller than
  17.             # the current result value. Also note that the current value of memo
  18.             # is what is being passed and not a new, empty dict:
  19.             new_result = dp_make_weight(egg_weights, target_weight - weight, memo)
  20.             if new_result < result:
  21.                 result = new_result
  22.         result += 1
  23.         memo[target_weight] = result
  24.         return result
  26. if __name__ == '__main__':
  27.     egg_weights = (1, 5, 10, 25)
  28.     n = 99
  29.     print("Egg weights =", egg_weights)
  30.     print("n =", n)
  31.     print("Expected output: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
  32.     print("Actual output:", dp_make_weight(egg_weights, n))
  34.     print()
  36.     egg_weights = (1, 6, 9, 12, 13, 15)
  37.     n = 724
  38.     print("Egg weights =", egg_weights)
  39.     print("n =", n)
  40.     print("Expected output: 49")
  41.     print("Actual output:", dp_make_weight(egg_weights, n))

输出：

  1. Egg weights = (1, 5, 10, 25)
  2. n = 99
  3. Expected output: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
  4. Actual output: 9
  6. Egg weights = (1, 6, 9, 12, 13, 15)
  7. n = 724
  8. Expected output: 49
  9. 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:

  1. def dp_make_weight(egg_weights, target_weight, memo=None):
  2.     if memo is None:
  3.         memo = {}
  5.     infinity = float(&#39;inf&#39;)
  7.     if target_weight &lt; 0:
  8.         return float(&#39;inf&#39;)
  9.     elif target_weight == 0:
  10.         return 0
  11.     else: # target_weight must be &gt; 0
  12.         if target_weight in memo:
  13.             return memo[target_weight]
  14.         result = infinity
  15.         for weight in egg_weights:
  16.             # Only update result when dp_make_weight returns a value smaller than
  17.             # the current result value. Also note that the current value of memo
  18.             # is what is being passed and not a new, empty dict:
  19.             new_result = dp_make_weight(egg_weights, target_weight - weight, memo)
  20.             if new_result &lt; result:
  21.                 result = new_result
  22.         result += 1
  23.         memo[target_weight] = result
  24.         return result
  26. if __name__ == &#39;__main__&#39;:
  27.     egg_weights = (1, 5, 10, 25)
  28.     n = 99
  29.     print(&quot;Egg weights =&quot;, egg_weights)
  30.     print(&quot;n =&quot;, n)
  31.     print(&quot;Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)&quot;)
  32.     print(&quot;Actual output:&quot;, dp_make_weight(egg_weights, n))
  34.     print()
  36.     egg_weights = (1, 6, 9, 12, 13, 15)
  37.     n = 724
  38.     print(&quot;Egg weights =&quot;, egg_weights)
  39.     print(&quot;n =&quot;, n)
  40.     print(&quot;Expected ouput: 49&quot;)
  41.     print(&quot;Actual output:&quot;, dp_make_weight(egg_weights, n))

Prints:

  1. Egg weights = (1, 5, 10, 25)
  2. n = 99
  3. Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
  4. Actual output: 9
  6. Egg weights = (1, 6, 9, 12, 13, 15)
  7. n = 724
  8. Expected ouput: 49
  9. Actual output: 49

huangapple
  • 本文由 发表于 2023年6月1日 17:41:05
  • 转载请务必保留本文链接：https://go.coder-hub.com/76380576.html
  • dynamic-programming
  • python
  • recursion
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定