2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] 動的計画法 ABC015D

Last updated at Posted at 2021-01-04

#ABC015D

個数制限付きのナップサック問題です。ちなみに全探索で考えると、N 個の中から K 個選んで入れる・入れないを全て試すと $O(2^N)$ となり、間に合いません。動的計画法であれば、計算量は $O(NKW)$ で間に合います。

動的計画法は部分問題を意識して、次のように設計します。

$dp[n][k][w]$の定義:
n 番目以下のスクリーンショットから k 枚以下のものを選び、幅が w を超えないように荷物を選んだ時の重要度の最大値

dpの漸化式:
$\mathrm {\rm dp}(n, k, w)$

=
\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初期条件:
$dp[0][0][*]=0$

求めるもの:
$dp[N][K][W]$

実装は、ボトムアップ方式の貰うDPで行います。Python では TLE ですが、PyPy では間に合いました。

サンプルコード
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] # 幅
            b = AB[n][1] # 重要度
            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])
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?