Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "034-038 Dynamic Programming: Knapsack DP".

2. Summary

dpHad a lot of trouble.bfs、dfsI had a lot of trouble, but more than thatdpI was worried until I understood a little. What I did was the same as for `BFS``` and DFS```, and while reading the explanation, debug line by line until I understood the example answer of `` `` AC```. I just follow. Also, I couldn't do `` DPof 100 carefully selected questions at first, so I first tried [Typical DP Contest](https://atcoder.jp/contests/tdpc/tasks)A ~ L After solving up to `` `(or rather, I understood while looking at the answer example), I started. Then, I was able to solve it a little.

3. Main story

034 --038 Dynamic programming: Knapsack DP basics

034. ALDS_10_A --Fibonacci number

Answer

n = int(input())
dp = [0] * (n + 1)

dp[0] = 1
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i - 1] + dp[i -2]

print(dp[n])

If you write it recursively as belowTLEBecause it does not pass``DP```It is a problem that you can see that you need to solve it with.

# This is TLE
num = int(input())

def fib(num):
    if num == 0:
        return 1
    if num == 1:
        return 1

    return fib(num - 1) + fib(num - 2)

print(fib(num))

035. DPL_1_B - 0,1 knapsack problem

####Answer

 N, W = map (int, input (). split ()) # N items, W is the capacity of weight
 p = [(0, 0)] + [tuple (map (int, input (). split ())) for _ in range (N)] # Goods-> (Value, Weight)
 dp = [[0] * (W + 1) for _ in range (N + 1)] # Vertical is the item number, horizontal is the current capacity, dp content is the maximum value

for i in range(1, N+1):
    for j in range(1, W+1):
        
        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i-1][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

It is a typical of the typical. There seems to be a way to write in 1D dp, but this is easier for me to write.

036. DPL_1_C -Knapsack problem

####Answer

 N, W = map (int, input (). split ()) # N is the type of item, W is the upper limit weight
 p = [(0, 0)] + [tuple (map (int, input (). split ())) for _ in range (N)] # (value, weight)
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, W+1):

        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

The difference from Problem 35 is that you can select the same type of product more than once, so I will modify the code only for that part. In particular,

dp[i][j] = max(dp[i-1][j],
               dp[i-1][j-p[i][1]] + p[i][0])

When

dp[i][j] = max(dp[i-1][j],
               dp[i][j-p[i][1]] + p[i][0])

so,maxThe contents are different. Problem 35 was in the form of "subtract the weight from the one before the subscript i and add your own value", while problem 36 is "subtract your own weight and add your own value".

037. DPL_1_A -Coin problem

####Answer

INF = float('inf')
n, m = map(int, input().split())
coins = [0] + list(map(int, input().split()))
dp = [[INF] * (n+1) for _ in range(m+1)]

dp[0][0] = 0

for i in range(1, m+1):
    for j in range(n+1):
        
        if j-coins[i] >= 0:
            dp[i][j] = min(dp[i-1][j-coins[i]] + 1,
                           dp[i][j-coins[i]] + 1,
                           dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[m][n])

The coin problem is also typical, and the idea is almost the same as the knapsack.

038. ALDS_10_C -Longest common subsequence

####Answer

# I can pass this, but I don't like it.
def main(A, B):
    dp = [0] * (len(B)+1)

    for a in A:
        before = dp[:]
        for j in range(1, len(B)+1):
            
            if a == B[j-1]:
                dp[j] = before[j-1] + 1
            elif dp[j] < dp[j-1]:
                dp[j] = dp[j-1]
                            
    return dp[-1]


if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        A = list(input())
        B = list(input())
        print(main(A, B))

Problem 34~If you write it in the same way as 37, it will be as follows. I like this because it's the easiest to write and it's also easy to restore the longest common subsequence. However, on the system, if you write as followsTLETherefore, the above answer was made by devising various ways to speed up the process.

# This is TLE. Restoration is easy.
q = int(input())

answer_list = []
for _ in range(q):
    A = [''] + list(input())
    B = [''] + list(input())
    dp = [[0] * (len(B)) for _ in range(len(A))]

    for i in range(1, len(A)):
        for j in range(1, len(B)):
            
            if A[i] == B[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],
                               dp[i-1][j])

    print(dp[len(A)-1][len(B)-1])

Especially for letter Afor i in range(1, len(A)):Compared to turning withfor a in A:It seems that it is faster to turn it around. After all, accessing the list with subscripts may be quite slow.