dp数组的元素值莫名其妙地被改变了

请问为什么我的dp数组的元素值被改变了


def ZeroOneKnapsack(dp, v, c):
    num = len(dp) - 1
    V = len(dp[0]) - 1
    for i in range(1, num+1):
        for j in range(1, V + 1):
            for (v1, c1) in zip(v[i-1], c[i-1]):
                if v1 > j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i-1][j-v1] + c1)
                    if dp[i][j] != dp[i][j - 1]:
                        print(dp[i-1][j], dp[i-1][j-v1] + c1)
                        print('dp[%d][%d] is %d' % (i, j, dp[i][j]))
    print('dp[3][200] is %d' % dp[3][200])
    return dp[num][V]

N, m = map(int, input().split())
N //= 10
# 主件到附件的索引
idx = [[] for _ in range(m)]
# 主件到原物品的索引
key = []
v = [0] * (m + 1)
c = [0] * (m + 1)
for i in range(1, m + 1):
    v[i], p, q = map(int, input().split())
    v[i] //= 10
    c[i] = v[i] * p
    if not q:
        key.append(i)
    else:
        idx[q-1].append(i)

m_key = len(key)
extend_v = [[] for _ in range(m_key)]
extend_c = [[] for _ in range(m_key)]
for i, k in enumerate(key):
    extend_v[i].append(v[k])
    extend_c[i].append(c[k])
    for k1 in idx[k-1]:
        extend_v[i].append(v[k] + v[k1])
        extend_c[i].append(c[k] + c[k1])
    if len(idx[k-1]) == 2:
        k1 = idx[k-1][0]
        k2 = idx[k-1][1]
        extend_v[i].append(v[k] + v[k1] + v[k2])
        extend_c[i].append(c[k] + c[k1] + c[k2])

print(extend_v)
print(extend_c)
dp = [[0] * (N + 1) for _ in range(m_key + 1)]
print(ZeroOneKnapsack(dp, extend_v, extend_c)*10)

你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7808468
这篇博客也不错, 你可以看下DP练习题：求解幸运数问题（递归思想，动规解决）
除此之外, 这篇博客: 强化学习（三）用动态规划（DP）求解中的 3. 策略评估求解实例 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
　　　　这是一个经典的Grid World的例子。我们有一个4x4的16宫格。只有左上和右下的格子是终止格子。该位置的价值固定为0，个体如果到达了该2个格子，则停止移动，此后每轮奖励都是0。个体在16宫格其他格的每次移动，得到的即时奖励RR都是-1。注意个体每次只能移动一个格子，且只能上下左右4种移动选择，不能斜着走, 如果在边界格往外走，则会直接移动回到之前的边界格。衰减因子我们定义为γ=1γ=1。由于这里每次移动，下一格都是固定的，因此所有可行的的状态转化概率P=1P=1。这里给定的策略是随机策略，即每个格子里有25%的概率向周围的4个格子移动。
　　　　首先我们初始化所有格子的状态价值为0，如上图k=0k=0的时候。现在我们开始策略迭代了。由于终止格子的价值固定为0，我们可以不将其加入迭代过程。在k=1k=1的时候，我们利用上面的贝尔曼方程先计算第二行第一个格子的价值：
v(21)1=14[(−1+0)+(−1+0)+(−1+0)+(−1+0)]=−1v1(21)=14[(−1+0)+(−1+0)+(−1+0)+(−1+0)]=−1
　　　　第二行第二个格子的价值是：
v(22)1=14[(−1+0)+(−1+0)+(−1+0)+(−1+0)]=−1v1(22)=14[(−1+0)+(−1+0)+(−1+0)+(−1+0)]=−1
　　　　其他的格子都是类似的，第一轮的状态价值迭代的结果如上图k=1k=1的时候。现在我们第一轮迭代完了。开始动态规划迭代第二轮了。还是看第二行第一个格子的价值：
v(21)2=14[(−1+0)+(−1−1)+(−1−1)+(−1−1)]=−1.75v2(21)=14[(−1+0)+(−1−1)+(−1−1)+(−1−1)]=−1.75
　　　　第二行第二个格子的价值是：
v(22)2=14[(−1−1)+(−1−1)+(−1−1)+(−1−1)]=−2v2(22)=14[(−1−1)+(−1−1)+(−1−1)+(−1−1)]=−2
　　　　最终得到的结果是上图k=2k=2的时候。第三轮的迭代如下：

v(21)3=14[(−1−1.7)+(−1−2)+(−1−2)+(−1+0)]=−2.425v3(21)=14[(−1−1.7)+(−1−2)+(−1−2)+(−1+0)]=−2.425
v(22)3=14[(−1−1.7)+(−1−1.7)+(−1−2)+(−1−2)]=−2.85v3(22)=14[(−1−1.7)+(−1−1.7)+(−1−2)+(−1−2)]=−2.85
　　　　最终得到的结果是上图k=3k=3的时候。就这样一直迭代下去，直到每个格子的策略价值改变很小为止。这时我们就得到了所有格子的基于随机策略的状态价值。
　　　　可以看到，动态规划的策略评估计算过程并不复杂，但是如果我们的问题是一个非常复杂的模型的话，这个计算量还是非常大的。