[Python] Dynamic programming ABC015D

ABC015D

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: \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 initial condition: dp[0][0][*]=0

What you want: dp[N][K][W]

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

[Python] Dynamic programming ABC015D
[Python] Dynamic programming knapsack problem
[Python] Dynamic programming TDPC D
[Python] ABC175D
[Python] Dynamic programming TDPC A
Python programming note
[Python] DP ABC184D
Python dynamic typing
Programming in python
Studying dynamic programming ①
[Python] UnionFind ABC177D
Learn dynamic programming in Python (A ~ E)
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
[Python] Interval scheduling ABC103D
3. 3. AI programming with Python
Competitive programming diary python 20201213
[Python] Binary search ABC155D
Python programming with Atom
Solve ABC159-D in Python
Competitive programming diary python 20201220
Python programming in Excel
LEGO Mindstorms 51515 Python Programming
Competitive programming diary python
Programming with Python Flask
[Python] Cumulative sum ABC179D
Programming with Python and Tkinter
Python Programming Workshop-Super Introductory Vol.3
[Python] BFS (breadth-first search) ABC168D
Python3 programming functions personal summary
Atcoder Acing Programming Contest Python
Python Selenium Dynamic download wait
Python web programming article summary
Paiza Python Primer 1 Learn Programming
[Python] DFS (Depth-first Search) ABC157D
Python Competitive Programming Site Summary
Python Machine Learning Programming> Keywords
Network programming with Python Scapy
[Python] Technique to reduce dimensions with DP (Dynamic Programming) [AtCoder]
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)
Memoization recursion and dynamic programming known by Python Fibonacci sequence
[Swift / Ruby / Python / Java] Object-oriented programming
Python3 standard input for competitive programming
GUI programming in Python using Appjar
Functional programming in Python Project Euler 1
[Introduction to Python3 Day 1] Programming and Python
Python
Competitive programming, coding test template: Python3
[Python] How to derive nCk (ABC156-D)
Functional programming in Python Project Euler 3
Dynamic proxy with python, ruby, PHP
[Python] Object-oriented programming learned with Pokemon
Functional programming in Python Project Euler 2
(Python) ABC162-D Consideration log and solution
python documentation reading socket programming HOWTO
Competitive programming with python Local environment settings
"Python AI programming" starting from 0 for windows
What kind of programming language is Python?
"Python Machine Learning Programming" Summary Note (Jupyter)