This is a knapsack problem with a limited number. By the way, if you think about it in a full search, if you select K out of N and try all of them, it will be $ O (2 ^ N) $, which is not in time. With dynamic programming, the amount of calculation is $ O (NKW) $.
Dynamic programming is designed with the subproblem in mind as follows.
Definition of $ dp [n] [k] [w] $: Maximum importance when selecting k or less from the nth or less screenshots and selecting luggage so that the width does not exceed w
dp recurrence formula:
=
\left \{
\begin{array}{l}
\mathrm {\rm max}\{ {\rm dp}( n - 1, k, w ), \:{\rm dp}( n - 1, k - 1, w - A_{n-1} ) + B_{k-1} \}&( k \geq A_{n-1} )\\
\mathrm {\rm dp}( n - 1, k, w ) &(otherwise)\\
\end{array}
\right.
dp initial condition:
What you want:
Implementation is done by the DP received from the bottom-up method. TLE in Python, but in time with PyPy.
Sample code
W = int(input())
N, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0]*(W+1) for _ in range(K+1)] for _ in range(N+1)]
for n in range(N):
for k in range(K+1):
for w in range(W+1):
a = AB[n][0] #width
b = AB[n][1] #importance
if w-a>=0 and k-1>=0:
dp[n+1][k][w] = max(dp[n][k][w], dp[n][k-1][w-a]+b)
else:
dp[n+1][k][w] = dp[n][k][w]
print(dp[N][K][W])
Recommended Posts