[Python] Dynamic programming TDPC A

TDPC A

Dynamic programming

The algorithm is as follows:

Solve using inductive relationships while recording calculation results

When applying to an optimization problem, in general, the following two problems must be met:

If these two points are met and the shape of the entire solution is unknown, dynamic programming is suitable. ** On the contrary, it is not suitable when the shape of the whole solution is clear. Note that it is not always appropriate because it is applicable. Subset sum problems can be thought of as reduced size problems. As an implementation, there are many formats in which an array of answers to partial problems is noted as dp.

Solving the problem

The subset sum problem is the following problem:

Select some of $ N $ positive integers $ a_0,…, a_ {N−14} $ and determine if the sum of them can be $ W $.

The problem this time is not to ask whether a concrete integer W can be created, but to find the number of integers that can be created. However, if the subset sum problem is solved, it is almost solved. This is because it can be determined whether the integer $ j $ can be created by looking at the array $ dp [N] [j] $ obtained by solving the partial sum problem. If you know the set of total points that can be made from the $ i-1 $ question, you can add the total points that can be added to the $ i $ question points $ p_i $ and the total points that can be made without adding them. You can see the set of total points that can be obtained from the questions up to the i $ question. At this time, if the total points are the same, it does not matter which combination of problems the score was created, so the number of partial problems to be solved can be reduced. (Dynamic programming) The external design by dynamic programming is as follows.

Definition of dp: Truth value of whether or not the sum of $ j $ points can be obtained by using the questions up to the $ i $ question. $0\leqq i \leqq N, 0 \leqq j \leqq \sum_i p_i$ Definition of dp recurrence formula:

dp[i][j]=\begin{cases}
        dp[i-1][j]\lor dp[i-1][j-p_i] & (j\ge p_i) \\
        dp[i-1][j] & (j\lt p_i)
        \end{cases}

dp initial condition:

dp[0][0]=1

Solution to be found: Number of elements for which $ dp [n] [j] $ is 1

Here, in the so-called "get DP", the recurrence formula was considered in the direction that the loop of i increases from 1 to n (** bottom-up method **), but the DP to be distributed and the loop of i are reversed (memoization). You can also think of ** top-down method **). I think that the fact that there are various solutions for the same DP is a factor in versatility and esotericity. By the way, with this recurrence formula, the array can be made one-dimensional by turning the loop of j in the direction of decreasing from MAX. The amount of calculation is $ O (NW) $, where $ W (≤10000) $ is the maximum integer that can be created.

Sample code


#Receiving input
N = int(input())
P = list(map(int, input().split()))

#Is it possible to get a total of j points using the questions up to the i-question (bool value)?
dp = []
#The 0th question is assumed to be in a state where no problem has been solved. There are N questions, so dp[N]Need up to
for i in range(N+1):
    dp.append([False] * (100 * 101))

#Using the questions up to the 0th question (=You can get 0 points (do not solve any problem).
#Also, since it will not be a score other than that, dp[0][0]Other than dp[0]The value of the array of is False.
dp[0][0] = True

#Loop from 1st question to Nth question
for i in range(1, N+1):
    # dp[i]To put a value in, dp[i-1]I will look at the state of
    for j, dpj in enumerate(dp[i-1]): #index,Get object
        if dpj is True:
            #Do not solve the i-question problem
            dp[i][j] = True

            #Solve the i-question problem
            #The score of the i question is P[i-1]Represented by
            dp[i][j+P[i-1]] = True

# dp[N]Looking at the array of, the total score that can be True
print(dp[N].count(True))

Recommended Posts

[Python] Dynamic programming TDPC A
[Python] Dynamic programming TDPC D
[Python] Dynamic programming ABC015D
Learn dynamic programming in Python (A ~ E)
[Python] Dynamic programming knapsack problem
Python programming note
Python dynamic typing
Programming in python
Studying dynamic programming ①
Try a functional programming pipe in Python
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
I made a competitive programming glossary with Python
[Python] Take a screenshot
Create a Python module
A python lambda expression ...
Daemonize a Python process
Python programming with Atom
Competitive programming diary python 20201220
Competitive programming with python
Python3> round (a --b, 7)
Competitive programming diary python
Programming with Python Flask
Building a Python environment for programming beginners (Mac OS)
AtCoder ABC 177 Python (A ~ E)
Programming with Python and Tkinter
Python Programming Workshop-Super Introductory Vol.3
Take a screenshot in Python
A Python program in "A book that gently teaches difficult programming"
Create a Wox plugin (Python)
Python3 programming functions personal summary
Create a function in Python
Create a dictionary in Python
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Atcoder Acing Programming Contest Python
AtCoder ABC 178 Python (A ~ E)
Try programming with a shell!
[Python] Use a string sequence
Python Selenium Dynamic download wait
AtCoder ABC 176 Python (A ~ E)
Python web programming article summary
Paiza Python Primer 1 Learn Programming
Python list is not a list
A memorandum about correlation [Python]
Make a bookmarklet in Python
Building a Python virtual environment
Create a python numpy array
Make a fortune with Python
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Python Competitive Programming Site Summary
Python Machine Learning Programming> Keywords
Python Programming Workshop-Super Introductory Vol.4
[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)
I made a python text
A memorandum about Python mock
Create a pixel art of Levi Captain with Python programming!
Memoization recursion and dynamic programming known by Python Fibonacci sequence
An introduction to Python Programming
AtCoder ABC 182 Python (A ~ D)
Build a Python environment offline
Draw a heart in Python