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.
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.
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