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)