управление потоком Python работает странно - PullRequest
Новая
       12

управление потоком Python работает странно

0 голосов
/ 18 мая 2018

Я пытался решить проблему ранца с помощью 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 также был изменен.Как будто внутри цикла было другое «для меня в диапазоне ()».У кого-нибудь есть идея, почему это происходит?Я запустил код с Python 3.6.1

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

В этой строке 

 dp = [[False] * (run_sum+1)] * (n+1)

* (n+1) волшебным образом не создает копии внутреннего списка.Вместо этого он просто составляет список (n+1) ссылок на тот же список.

0 голосов
/ 18 мая 2018

Эта строка 

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)]
...