python 动态规划 01背包问题 遇到一个小问题?

Python 01背包问题:为什么我把numpy替换成***数组结果不一样呢,希望大佬们请教
# dynamic programming in 0-1 Knapsack Problem
import numpy as np

# n: 对象个数
# W: 总重量
# w: 每个物品的重量大小
# v: 每个物品的价值大小
# return: 返回最大价值

"""用了numpy"""
def Knapsack_01_0(n, W, w, v):
    # create (n+1)*(W+1) table initialized with all 0
    dp = np.array([[0]*(W+1)]*(n+1))

    # using DP to solve 0-1 Knapsack Problem
    for i in range(1, n+1):
        for j in range(1, W+1):
            # if ith item's weight is bigger than j, then do nothing
            if w[i-1] > j:
                dp[i,j] = dp[i-1, j]
            else: # compare the two situations: putt ith item in or not
                dp[i,j] = max(dp[i-1, j], v[i-1] + dp[i-1, j-w[i-1]])

    return dp[n][W] # maximum value of 0-1 Knapsack Problem



"""没用numpy"""
def Knapsack_01_1(n, W, w, v):
    # create (n+1)*(W+1) table initialized with all 0
    dp = [[0]*(W+1)]*(n+1)
    # using DP to solve 0-1 Knapsack Problem
    for i in range(1, n+1):#遍历每行
        for j in range(1, W+1):#遍历每列
            # if ith item's weight is bigger than j, then do nothing
            if w[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else: # compare the two situations: put ith item in or not
                dp[i][j] = max(dp[i-1][j], v[i-1] + dp[i-1][j-w[i-1]])
    return dp[n][W]# maximum value of 0-1 Knapsack Problem


def main():
    # test
    W = 20
    w = (1, 2, 5, 6, 7, 9)
    v = (1, 6, 18, 22, 28, 36)
    n = len(w)

    max_value_0 = Knapsack_01_0(n, W, w, v)
    print('use numpy Max value : %s'%max_value_0)
    
    max_value1 = Knapsack_01_1(n, W, w, v)
    print('no use numpy Max value : %s'%max_value1)

main()

#笔试题目#
全部评论
第31行不能这么写,改成这样应该就行 dp = [[0 for i in range(W+1)] for i in range(n+1)]
点赞 回复 分享
发布于 2018-10-09 11:01
在初始化数组的时候 要注意***数组如果用乘法复制的话 那么它们是占相同的内存的
点赞 回复 分享
发布于 2018-10-09 11:04

相关推荐

害怕一个人的小黄鸭胖乎乎:笑死了,没有技术大牛,招一堆应届生,不到半年,代码就成屎山了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务