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

查看13道真题和解析