There are $ N $ types of items that weigh $ v_i $ and weigh $ w_i $, and knapsacks that weigh $ W $.
Select the item and put it in the knapsack so that the following conditions are met:
When applying to an optimization problem, in general, the following two problems must be met:
Find the maximum total value.
The external design by dynamic programming is as follows.
Definition of $ dp [i + 1] [j] $: The maximum value of the total value when the total weight is selected to be $ j $ or less from the items up to the $ i $ question.
dp initial condition:
dp[0][j]=1
Definition of dp recurrence formula:
dp[i+1][j]=max\{dp[i][j-k×w[i]]+k×v[i] \}
This would result in a triple loop, so the amount of calculation would be $ O (nW ^ 2) $, which is time over. By transforming the recurrence formula, the loop of $ k $ can be eliminated and the amount of calculation can be $ O (nW) $. This variant is intended to eliminate duplicate calculations in information processing. The way to understand is to find $ dp [i + 1] [j] $, not from $ dp [i] [*] $, which is one step before, but $ dp [i] [j] $ and $ dp [ It's enough to look at i + 1] [jw [i]] + v [i] $, and vice versa. The explanation of the ant book is easy to understand.
Transformation of dp recurrence formula:
dp[i+1][j]=max(dp[i][j], dp[i+1][j-w[i]]+v[i])
Solution: $ dp [n] [W] $
Sample code
n = int(input())
w = []
v = []
for i in range(n):
w_, v_ = map(int, input().split())
w.append(w_)
v.append(v_)
W = int(input())
dp = [[0] * (W + 1) for i in range(n + 1)]
for i in range(n):
for j in range(W + 1):
if j < w[i]:
dp[i + 1][j] = dp[i][j]
else:
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
print(dp[n][W])
Recommended Posts