我试图使用 DP 解决背包问题。基本上,目标是看看列表中的某些元素的总和是否可以达到总和的一半。
def canPartition(nums):
"""
:type nums: List[int]
:rtype: bool
"""
run_sum = 0
for num in nums:
run_sum += num
if run_sum & 1 == 1:
return False
run_sum //= 2
n = len(nums)
dp = [[False] * (run_sum+1)] * (n+1)
for i in range(n+1):
dp[i][0] = True
for j in range(1, run_sum+1):
dp[0][j] = False
print("initial stage")
print(dp)
for i in range(1, 2):
for j in range(1, run_sum+1):
dp[i][j] = dp[i-1][j]
print("inner loop after operation 1:")
print(dp)
if j >= nums[i-1]:
print("inner loop after operation 2:")
print(i, j)
dp[i][j] |= dp[i-1][(j - nums[i-1])]
print(dp)
print(" ")
return dp[n][run_sum]
nums = [1, 2, 5]
canPartition(nums)
目标本身在这里并不那么重要。但是最后一个嵌套循环的流程控制表现得非常奇怪。下面是打印结果。
initial stage
[[True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False]]
inner loop after operation 1:
[[True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False], [True, False, False, False, False]]
inner loop after operation 2:
1 1
[[True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False]]
inner loop after operation 1:
[[True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False], [True, True, False, False, False]]
inner loop after operation 2:
1 2
[[True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False]]
inner loop after operation 1:
[[True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False], [True, True, True, False, False]]
inner loop after operation 2:
1 3
[[True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False]]
inner loop after operation 1:
[[True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False], [True, True, True, True, False]]
inner loop after operation 2:
1 4
[[True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True]]
您可以看到,即使整个嵌套循环中 i 的值为 1,dp[i>1] 的值也会在循环中以某种方式被修改。甚至j也从1修改为4。就像循环内还有另一个“for i in range()”。有谁知道为什么会发生这种情况?我用 python 3.6.1 运行了代码
最佳答案
这一行
dp = [[False] * (run_sum+1)] * (n+1)
创建一个包含 n + 1
个引用的列表,对 False
的相同列表进行引用。一个更简单的例子:
>>> x = [[False]]*3
>>> x
[[False], [False], [False]]
>>> x[0][0] = True
>>> x
[[True], [True], [True]]
你几乎不想将 *
与列表一起使用;使用列表理解来获取独立列表:
dp = [[False for _ in range(run_sum+1)] for _ in range(n+1)]
关于python流控制功能奇怪,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50417851/