ナップザック問題 解法１
# 全n個の品物のうち、i番目以降の品物から、重さの総和が j 以下になるように選ぶ
def question18(i, j):
if i == n:
return 0
elif j < W[i]:
return question18(i + 1, j)
else:
return max(question18(i + 1, j), question18(i + 1, j - W[i]) + V[i])
n = 5
x = 175
W = [95, 56, 65, 54, 32]
V = [79, 9, 57, 55, 27]
question18(0, x)
139
n = 10
x = 492
W = [53, 64, 82, 93, 76, 67, 10, 6, 82, 91]
V = [80, 16, 30, 68, 31, 19, 50, 64, 20, 96]
question18(0, x)
438
n = 20
x = 1371
W = [30, 31, 100, 83, 52, 97, 34, 70, 96, 13, 70, 89, 79, 51, 31, 93, 73, 10, 77, 31]
V = [31, 58, 49, 75, 1, 57, 8, 1, 35, 22, 82, 28, 61, 46, 68, 10, 32, 84, 19, 16]
question18(0, x)
783
n = 40
x = 2250
W = [96, 64, 21, 86, 49, 72, 4, 90, 91, 91, 43, 95, 89, 23, 38, 58, 29, 43, 27, 3, 47, 29, 5, 90, 46, 100, 94, 56, 49, 62, 46, 51, 41, 28, 47, 61, 28, 100, 91, 80]
V = [74, 83, 57, 64, 63, 58, 100, 59, 66, 66, 85, 55, 86, 25, 41, 64, 26, 1, 87, 88, 73, 98, 57, 63, 31, 69, 21, 79, 96, 13, 2, 50, 89, 10, 11, 93, 45, 31, 15, 67]
# question18(0, x)
n = 40 になってくると、そろそろ計算時間的に無理になる
解法２
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
def question18(i, j):
if dp_table[i][j] >= 0:
return dp_table[i][j]
elif i == n:
ret = 0
elif j < W[i]:
ret = question18(i + 1, j)
else:
ret = max(question18(i + 1, j), question18(i + 1, j - W[i]) + V[i])
dp_table[i][j] = ret
return ret
n = 5
x = 175
W = [95, 56, 65, 54, 32]
V = [79, 9, 57, 55, 27]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
139
n = 10
x = 492
W = [53, 64, 82, 93, 76, 67, 10, 6, 82, 91]
V = [80, 16, 30, 68, 31, 19, 50, 64, 20, 96]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
438
n = 20
x = 1371
W = [30, 31, 100, 83, 52, 97, 34, 70, 96, 13, 70, 89, 79, 51, 31, 93, 73, 10, 77, 31]
V = [31, 58, 49, 75, 1, 57, 8, 1, 35, 22, 82, 28, 61, 46, 68, 10, 32, 84, 19, 16]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
783
n = 40
x = 2250
W = [96, 64, 21, 86, 49, 72, 4, 90, 91, 91, 43, 95, 89, 23, 38, 58, 29, 43, 27, 3, 47, 29, 5, 90, 46, 100, 94, 56, 49, 62, 46, 51, 41, 28, 47, 61, 28, 100, 91, 80]
V = [74, 83, 57, 64, 63, 58, 100, 59, 66, 66, 85, 55, 86, 25, 41, 64, 26, 1, 87, 88, 73, 98, 57, 63, 31, 69, 21, 79, 96, 13, 2, 50, 89, 10, 11, 93, 45, 31, 15, 67]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
2260
n = 80
x = 2685
W = [7, 32, 92, 96, 96, 77, 49, 84, 80, 22, 14, 87, 4, 61, 27, 90, 23, 98, 59, 80, 25, 45, 14, 46, 41, 72, 86, 40, 27, 97, 96, 52, 86, 85, 55, 48, 92, 69, 57, 89, 2, 63, 20, 80, 98, 85, 31, 86, 65, 87, 94, 27, 95, 43, 27, 24, 65, 9, 81, 53, 36, 43, 14, 98, 85, 9, 66, 45, 49, 10, 68, 19, 5, 61, 53, 76, 75, 75, 55, 36]
V = [71, 6, 45, 90, 41, 89, 5, 57, 19, 78, 79, 100, 9, 45, 84, 41, 90, 18, 100, 34, 60, 6, 7, 82, 64, 40, 17, 44, 85, 94, 33, 90, 36, 50, 46, 66, 6, 57, 36, 4, 15, 50, 23, 94, 99, 26, 33, 95, 16, 45, 6, 93, 37, 89, 13, 52, 4, 92, 86, 10, 41, 12, 85, 43, 98, 92, 57, 38, 75, 61, 66, 1, 74, 61, 91, 33, 35, 96, 13, 17]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
3594
n = 100
x = 1913
W = [17, 22, 91, 12, 12, 76, 56, 86, 63, 42, 26, 15, 8, 11, 99, 60, 30, 90, 35, 92, 10, 49, 39, 58, 60, 80, 28, 9, 47, 43, 87, 55, 54, 46, 33, 50, 67, 52, 2, 51, 6, 50, 1, 83, 64, 58, 47, 63, 99, 6, 65, 17, 11, 99, 94, 23, 75, 8, 87, 44, 40, 53, 60, 69, 2, 74, 73, 44, 77, 21, 30, 51, 50, 63, 64, 21, 72, 6, 28, 19, 78, 38, 71, 68, 84, 92, 60, 34, 63, 17, 86, 22, 79, 48, 98, 40, 39, 41, 72, 30]
V = [47, 44, 4, 11, 94, 44, 20, 2, 61, 59, 31, 20, 87, 18, 16, 79, 2, 2, 58, 31, 67, 35, 19, 39, 30, 15, 63, 31, 70, 13, 35, 50, 20, 18, 6, 8, 49, 13, 44, 60, 65, 5, 51, 15, 84, 74, 50, 34, 35, 91, 97, 18, 54, 27, 3, 29, 86, 44, 74, 94, 85, 75, 92, 66, 83, 34, 63, 74, 8, 62, 25, 68, 45, 59, 28, 54, 75, 98, 8, 35, 98, 42, 22, 51, 48, 43, 29, 73, 68, 41, 78, 62, 61, 4, 44, 91, 10, 35, 22, 51]
dp_table = [[-1 for _ in range(x + 1)] for _ in range(len(W) + 1)]
question18(0, x)
3388