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()
#笔试题目#