0-1バックパックコード
10266 ワード
説明文字は、以下のように参照されます.https://www.jianshu.com/p/25f4a183ede5
最適化:
import numpy as np
def zero_one_bag(n,w,v,C):
#
m = np.zeros((n+1, C+1))
for i in range(1,m.shape[0]): # i=1,2,3
for j in range(1, m.shape[1]): # j=0,1,2,3,4,5
if j < w[i-1]:
m[i,j] = m[i-1,j]
else:
m[i,j] = max(m[i-1,j], m[i-1, j-w[i-1]]+v[i-1])
return m[n,C]
n = int(input()) #
w = [int(x) for x in input().split(',')]
v = [int(x) for x in input().split(',')]
C = int(input()) #
a = zero_one_bag(n,w,v,C)
print(a)
最適化:
import numpy as np
def zero_one_bag(n,w,v,C):
# m = np.zeros((C)+1,dtype=np.int32)
m = np.zeros((C)+1)
for i in range(1,n):
for j in range(C,0,-1): # j=5,4,3,2,1
if w[i] <= j:
m[j] = max(m[j],m[j-w[i]]+v[i])
return m[-1]
n = 3
w = [1,2,3]
v = [6,10,12]
C = 5
result = zero_one_bag(n,w,v,C)
print(result)