Change to a style that is added by editing for each section.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
################naive full search########################
def val_tot(i, j):
if i == n:
res = 0
elif j < w[i]:
res = val_tot(i+1,j)
else:
res = max(val_tot(i+1,j), val_tot(i+1, j-w[i]) + v[i])
return res
print val_tot(0, W)
################Memoization########################
import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
def val_tot_memo(i, j):
if val_tot_list[i,j] !=-1:
return val_tot_list[i,j]
else:
if i == n:
res = 0
elif j < w[i]:
res = val_tot_memo(i+1,j)
else:
res = max(val_tot_memo(i+1,j), val_tot_memo(i+1, j-w[i]) + v[i])
val_tot_list[i,j] = res
return res
print int(val_tot_memo(0, W))
################Recurrence formula(DP) ########################
## dp[i][j] = dp[i+1][j]( w[i] > j)
## = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])
## val_tot_list[n,W] = 0
# import numpy as np
val_tot_list = -1*np.ones((n+1,W+1))
val_tot_list[n,:] = 0*val_tot_list[n,:]
for i in range(n-1,-1,-1):
for j in range(W+1):
if i ==n:
val_tot_list[n,j] = 0
else:
if w[i] > j:
val_tot_list[i][j] = val_tot_list[i+1][j]
else:
val_tot_list[i][j] = max(val_tot_list[i+1][j], val_tot_list[i+1][j - w[i]] + v[i])
print int(val_tot_list[0][W])
The amount of calculation is O (2 ^ n), O (nW), O (nW), respectively. I'm not used to suddenly formulating a recurrence formula and bringing it to the code (I think I'll make a mistake in the subscript), so I'd like to learn to write a naive full search and then make a memo.
# -*- coding: utf-8 -*-
s = raw_input()
t = raw_input()
#### dp[i][j]:Maximum common subsequence length for strings before the i-th and before the j-th of t
########################## naive #########################
def lcs(i,j):
if i == 0 or j == 0:
return 0
else:
if s[i-1] == t[j-1]:
return lcs(i-1,j-1) + 1
else:
return max(lcs(i-1,j-1+1), lcs(i-1+1,j-1))
print lcs(len(s),len(t))
##########################Memoization##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
def lcs_memo(i,j):
if lcs_list[i][j] != -1:
return lcs_list[i][j]
else:
if i == 0 or j == 0:
lcs_list[i][j] = 0
return 0
else:
if s[i-1] == t[j-1]:
lcs_list[i][j] = lcs_memo(i-1,j-1)+1
else:
lcs_list[i][j] = max([lcs_memo(i-1,j-1+1), lcs_memo(i-1+1,j-1)])
return lcs_list[i][j]
print lcs_memo(len(s),len(t))
########################## DP ##################################
import numpy as np
lcs_list = -1*np.ones((len(s)+1, len(t)+1),dtype = int)
lcs_list[0,:] = 0*lcs_list[0,:]
lcs_list[:,0] = 0*lcs_list[:,0] # initialize
for i in range(len(s)):
for j in range(len(t)):
if s[i] == t[j]:
lcs_list[i+1,j+1] = lcs_list[i,j]+1
else:
lcs_list[i+1,j+1] = np.max([lcs_list[i+1,j], lcs_list[i,j+1] ])
print lcs_list[-1,-1]
He said, "I want to learn to write a naive full search and then make a memo." However, DP was the easiest to write on this issue. Unlike the case of the knapsack problem, the loops of i and j were in the forward direction, so it seems that the initialization was easy to understand.
The other two were a bit confused by the association between the lcs argument and the array indexing.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#### dp[i][j] :Maximum value when the weight is j or less in the combination of items up to the i-th,The final calculation result is d[n][W]
####Initial value d[0][:] = 0, dp[:][0] = 0 (w_i >=Because it is 1)
####The recurrence formula is dp[i+1][j] = max(dp[i][j-k*w[i]] + k*v[i]| k ...ith Number of items)
##########################Full search############################
def dp(i,j):
if i <= 0 or j <= 0:
return 0
else:
return max([dp(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
print dp(n, W)
##########################Memoization############################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
def dp_memo(i,j):
if dplist[i,j] != -1:
return dplist[i,j]
else:
if i <= 0 or j <= 0:
dplist[i,j] = 0
return 0
else:
dplist[i,j] = max([dp_memo(i-1,j-k*w[i-1])+ k*v[i-1] for k in xrange(j//w[i-1] + 1)])
return dplist[i,j]
print dp_memo(n,W)
############################ DP_1 ##########################
import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
dplist[i+1,j] = max([dplist[i,j-k*w[i]]+k*v[i] for k in xrange(j//w[i]+1)])
print dplist[n][W]
############################ DP_2 ##########################
# import numpy as np
dplist = -1*np.ones((n+1, W+1),dtype=int)
dplist[0,:] = 0
dplist[:,0] = 0
for i in xrange(n):
for j in xrange(W+1):
if j < w[i]: #### i+The first item no longer fits
dplist[i+1,j] = dplist[i,j]
else:
dplist[i+1,j] = max(dplist[i,j], dplist[i+1,j-w[i]] + v[i]) ####Modification of recurrence formula(page 59).Loops can be reduced.
print dplist[n][W]
As in the ant book, if you write DP as it is from the recurrence formula, the loop will be tripled. A double loop can be created by avoiding duplicate calculations by transforming the recurrence formula.
Even if you make a memo, it is still looping, so it seems that processing is necessary anyway. I've used numpy just because it's easy to handle arrays, but I think it's better to be able to write with only the built-in stuff.
# -*- coding: utf-8 -*-
n = int(raw_input())
w = map(int,raw_input().split())
v = map(int,raw_input().split())
W = int(raw_input())
#########When the target of DP is changed from value to weight in response to the case where the weight constraint is tight##########
########## dp[i + 1][j]:The minimum weight when the price is j up to the i-th item
###########The final output is dp[n][j] <=Maximum j that meets W
###########The recurrence formula is dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i])
###########The initial value is dp[0][0] = 0, dp[0][j] = INF =float("INF")
###################Full search################
def dp(i,j):
if i == 0 and j == 0:
return 0
elif j != 0 and i == 0:
return float("INF")
else:
if j < v[i-1]:
return dp(i-1,j)
else:
return min(dp(i-1,j), dp(i-1,j-v[i-1])+w[i-1])
res = 0
for j_val in xrange(sum(v)):
if dp(n,j_val) <= W:
res = j_val
print res
###################Memoization################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
def dp_memo(i,j):
if i == 0 and j == 0:
dplist[i,j] = 0
return 0
elif j != 0 and i == 0:
return float("INF")
elif dplist[i,j] != -1:
return dplist[i,j]
else:
if j < v[i-1]:
dplist[i,j] = dp_memo(i-1,j)
return dplist[i,j]
else:
dplist[i,j] = min(dp_memo(i-1,j), dp_memo(i-1,j-v[i-1])+w[i-1])
return dplist[i,j]
res = 0
for j_val in xrange(sum(v)):
if dp_memo(n,j_val) <= W:
res = j_val
print res
################### DP ##################
import numpy as np
dplist = np.ones((n+1, sum(v)+1)) * (-1)
dplist[0,:] = float("INF")
dplist[0,0] = 0
for i in xrange(n):
for j in xrange(sum(v) +1):
if j < v[i]:
dplist[i+1,j] =dplist[i,j]
else:
dplist[i+1,j] = min(dplist[i,j], dplist[i,j-v[i]]+w[i])
res = 0
for j_val in xrange(sum(v)):
if dplist[n,j_val] <= W:
res = j_val
print res
This is also the easiest to write DP.
The recurrence formula is either dp [i] = hogehoge (dp [i + 1]) or dp [i + 1] = hogehoge (dp [i]).
The former is easier when writing using recursion, and the latter is easier when writing with DP (less confusion with array and function arguments). It seems better to change the recurrence formula that is set up according to which one you write. Even in the current problem, if dp [i, j] is "the i-th and subsequent items", Since the recurrence formula is dp [i, j] = min (dp [i + 1, j], dp [i + 1, j-v [i]] + w [i]), it is easy to write in recursion.
# -*- coding: utf-8 -*-
n = int(raw_input())
a = map(int,raw_input().split())
m = map(int,raw_input().split())
K = int(raw_input())
import numpy as np
################ dp[i+1][j]:Maximum number of i-ths left when making j up to i-th
################The recurrence formula is dp[i+1][j] = dp[i+1][j-a[i]] -1
################ = -1
################ = m[i] (dp[i][j] >= 0)
################If you can't make it-Put 1
dplist = np.ones((len(a)+1,K+1))*(-1)
dplist[0,0] = 0
for i in range(len(a)):
for j in range(K+1):
if dplist[i,j] >= 0:
dplist[i+1,j] = m[i]
elif dplist[i+1,j-a[i]]<= 0:
dplist[i+1,j] = -1
elif j - a[i] < 0:
dplist[i+1,j] = -1 ####### j - a[i] <When it is 0, it does not change whether j can be created even if the i-th is entered.(i-1)If it can be made up to the second, it is processed, so you only have to think about it here if you can not make it.
else:
dplist[i+1][j] = dplist[i+1,j-a[i]] -1
print dplist[n,K] >= 0
DP for bool seems to be wasteful.
In the bool value DP on page 62, it is written that it is a triple loop because there is a loop that processes how many a [i] are inserted (O (K \ sum_i m [i]), but O (nK) \ sum_i m [i]) seems to be correct).
As was the case with the unlimited number knapsack problem, it seems better to think that there is some waste if a triple loop appears. Think about how to eliminate the loop about the number of a [i].
In bool's DP, which is dp [i + 1] [j], whether j can be made up to the i-th The process of "dp [i + 1, j-k * a [i]] == is there a true k?" Is the cause of the triple loop. Therefore, if dp [i + 1] [j] can be determined using the result of dp [i + 1, j-a [i]], the triple loop becomes unnecessary.
However, if you have only a bool value, even if dp [i + 1, ja [i]] = True is given, you cannot know "whether a [i] still remains", so dp [i + 1 , j] can't be judged and it becomes a squirrel to turn the loop. Then, the idea seems to be that you should have the remaining number of a [i] as an array.
As expected, there is not enough training to get to this point from the problem statement. Is it a good idea to write (think) in a straightforward (stupid) way and look for improvements (maybe it's just a basic problem so remember the pattern)?
# -*- coding: utf-8 -*-
import numpy as np
a = map(int,raw_input().split())
#####################page 63#########################
### dp[i]: a[i]Is the length of the longest common subsequence at the end
dp = np.ones(len(a),dtype = int) * (-1)
dp[0] = 0
res = 0
for i in range(len(a)):
dp[i] = 1
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i],dp[j] + 1)
res = max(res,dp[i])
print res
#####################page 64: O(n^2)#########################
### dp[i]:Length i+Minimum value of the last element of a subsequence of 1
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
for i in xrange(n):
if i == 0 or dp[i-1] <a[j]:
dp[i] = min(dp[i],a[j])
print len(dp[dp<float("INF")])
#####################page 65: O(n log n)#########################
import bisect #### C++Lower in_To achieve the same behavior as bound.
dp = np.ones(len(a),dtype = int) * float("INF")
n = len(a)
for j in xrange(n):
dp[bisect.bisect_left(dp,a[j])] = a[j]
print len(dp[dp<float("INF")])
The bottom two are difficult.
For the time being, in the case of the policy of page 64, if you turn the loop for j, the array will be filled as follows.
a = {2,1,3,2}
Think about how the dp table should be updated when you add a new value to the end of a.
First, dp [0] is an increasing subsequence of length 1, so we just need to bring in the new minimum element of a.
dp [1] is the smallest element at the end of an increasing subsequence of length 2. Whether or not the value is updated by adding a new element can be decided by the dp [1] in a before the addition and the smaller of the new elements. However, if dp [0] has been updated with a new element, the new element cannot be at the end of the increasing subsequence and is excluded (if i == 0 or dp [i-1] <a [j]. ] Part).
For dp [2], suppose dp [1] is updated with a new element. At this time, if dp [2] is also updated, there is a smaller value that comes to the end of the subsequence of length 2, which is a contradiction. So, compare the new element with the original dp [1] only if dp [1] has not been updated.
So, in general, if you add a new element to a, dp [i] should only be updated with min (dp [i], a_new) if dp [i-1] has not been updated with that value. Good.
If the initial value is given by INF, it is sufficient to loop around the element of a and judge from the beginning of dp as described above. This is the answer in O (n ^ 2).
The method using the binary search on page 65 is that the part to be judged from the beginning of dp is O (log n). The final dp array has monotonically increasing values, so we don't need to look at dp [i] less than a [j]. Therefore, you can search for i such that dp [i]> = a [j] by bisect.bisect_left (lower_bound in STL). From the search method, dp [i-1] <a [j], dp [i] = min (dp [i], a [j]) = a [j] is automatically satisfied, so the condition is judged. It can be updated with dp [i] = a [j] without doing anything.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
M = int(raw_input())
####### dp[i][j]Let be the number of methods when dividing i into j.
#######The recurrence formula is dp[i][j] = dp[i-j][j] + dp[i][j-1]
dp = np.zeros((n+1,m+1),dtype = int)
dp[:,1] = 1
for i in xrange(n+1):
for j in xrange(2,m+1):
if i-j >=0:
dp[i][j] = dp[i][j-1] + dp[i-j][j]
else:
dp[i][j] = dp[i][j-1]
print dp[-1][-1]
I first thought of a recurrence formula that felt like thinking about the rest of the boxes with the largest number of boxes, but it didn't work because of duplication. I might have been able to eliminate the duplication if I did it well, but it's not good because it became O (mn ^ 2) anyway. (Insufficient math skills before programming)
I'm used to dropping recurrence formulas into code.
# -*- coding: utf-8 -*-
import numpy as np
n = int(raw_input())
m = int(raw_input())
a = map(int,raw_input().split())
M = int(raw_input())
dp = np.zeros((n+1,m+1),dtype = int)
dp[0,:a[0]] = 1
dp[:,0] = 1
for i in xrange(n):
for j in xrange(1,m+1):
if j -1 - a[i] >=0:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j] -dp[i][j-1-a[i]]
else:
dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
print dp[-1][-1]
The recurrence formula is simple, but how do you reduce the amount of calculation from it? In order to erase the triple loop, it is necessary to rewrite the sum with the amount already calculated.
The implementation power, or the part of writing code in DP from the recurrence formula, has become smoother. It feels like Kang is starting to work for misassignment of subscripts.
It is still necessary to practice the part of formulating an appropriate and small-complexity recurrence formula. When I think about it, I was a little weak at combinatorics from the time I took the exam.
At the end of Chapter 2, the POJ question number is listed as an exercise, so I'd like to do that as well.