プログラミング問題集解答例（問２０）

def question20(x, W, V):
    dp_table = [[0 for _ in range(x + 1)] for _ in range(len(W) + 1)]
    for i in range(len(W)):
        for j in range(x + 1):
            if j < W[i]:
                dp_table[i + 1][j] = dp_table[i][j]
            else:
                dp_table[i + 1][j] = max(dp_table[i][j], dp_table[i + 1][j - W[i]] + V[i])
    return dp_table[len(W)][x]

n = 3
W = [3, 4, 2]
V = [4, 5, 3]
x = 7

question20(x, W, V)

10

n =  10
x =  867
W =  [28, 92, 30, 1, 40, 33, 96, 30, 38, 86]
V =  [6, 77, 53, 91, 47, 33, 28, 28, 78, 36]

question20(x, W, V)

78897

n =  20
x =  1272
W =  [10, 87, 38, 74, 19, 93, 34, 24, 63, 12, 31, 99, 45, 4, 22, 81, 50, 75, 36, 20]
V =  [1, 96, 33, 97, 58, 31, 68, 60, 23, 60, 27, 7, 24, 70, 60, 73, 11, 88, 87, 71]

question20(x, W, V)

22260

n =  40
x =  3309
W =  [20, 5, 85, 84, 10, 15, 80, 24, 48, 96, 33, 18, 22, 58, 62, 24, 12, 73, 76, 9, 53, 7, 47, 82, 69, 82, 57, 33, 60, 10, 84, 16, 97, 9, 57, 92, 22, 1, 70, 26]
V =  [83, 17, 72, 71, 40, 16, 94, 78, 41, 43, 38, 21, 3, 35, 58, 59, 63, 75, 5, 64, 75, 30, 48, 45, 69, 7, 25, 37, 80, 70, 93, 68, 41, 34, 60, 39, 8, 86, 64, 27]

question20(x, W, V)

284574

n =  40
x =  1747
W =  [60, 76, 2, 14, 89, 88, 83, 27, 55, 10, 53, 58, 60, 45, 90, 73, 32, 54, 90, 97, 28, 54, 10, 70, 73, 61, 5, 14, 35, 65, 57, 12, 9, 85, 98, 51, 49, 13, 98, 16]
V =  [23, 25, 14, 1, 39, 18, 16, 81, 67, 75, 14, 23, 95, 58, 47, 99, 33, 100, 9, 19, 57, 52, 36, 16, 30, 83, 99, 61, 97, 74, 16, 27, 70, 81, 84, 13, 28, 14, 12, 27]

question20(x, W, V)

34565