参考 https://blog.csdn.net/yuxin6866/article/details/52507623
动态规划
view
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#动态规划之背包问题
#问题描述：一个包，承重量为V，N件物品，第i件物品重量c_i价值w_i。问：可装最大价值
#数学模型：已知A_{2*(N+1)}，第一行价值，第二行重量
# 一个f_{(N+1)*V}记录矩阵，初值f(1,j)=0
# 子问题：f(i,v)=max{f(i-1,j),f(i-1,v-c_i)+w_i}
N=5
V=120
A=[[0,40,50,70,40,20],[0,10,25,40,20,10]]
f=[[0 for j in range(V+1)] for i in range(N+1)]
for i in range(N+1):
for j in range(V+1):
if A[0][i]>j:
f[i][j]=f[i-1][j]
else:
f[i][j]=max(f[i-1][j],f[i-1][j-A[0][i]]+A[1][i])
print(f[N][V])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#动态规划之最长公共子序列LCS(Longest Common Subsequence)
#问题描述：cnblogs与belong，最长公共子序列为blog
#数学模型：两个序列为s_i，n_i=len(s_i)，i=1,2
# f_{(n_1+1)*(n_2+1)}
# 初值：f(0,j)=f(i,0)=0
# 状态转移：
# 若s_1[i]=s_2[j],则f(i,j)=f(i-1,j-1)+1
# 否则 f(i,j)=max{f(i,j-1),f(i-1,j)}
#并给出所有LCS
s_1='cnblogs'
s_2='belong'
n_1=len(s_1)
n_2=len(s_2)
f=[[0 for j in range(n_2+1)] for i in range(n_1+1)]
for i in range(1,n_1+1):
for j in range(1,n_2+1):
if s_1[i-1]==s_2[j-1]:
f[i][j]=f[i-1][j-1]+1
else:
f[i][j]=max(f[i-1][j],f[i][j-1])
print(f[n_1][n_2])#LCS的最大长度
######求LCS
s=[]
t=[]
W=[]
#####
#公共子串
#问题描述：cnblogs与belong，最长公共子串为lo
# 状态转移：
# 若s_1[i]=s_2[j],则f(i,j)=f(i-1,j-1)+1
# 否则 f(i,j)=0
#并给出所有最长公共子串
lenn=0
g=[[0 for j in range(n_2+1)] for i in range(n_1+1)]
for i in range(1,n_1+1):
for j in range(1,n_2+1):
if s_1[i-1]==s_2[j-1]:
g[i][j]=g[i-1][j-1]+1
lenn=max(g[i][j],lenn)
else:
f[i][j]==0
print(lenn)#LCS的最大长度
######求公共子串
s=[]
t=[]
W=[]
#####
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#动态规划之KMP算法
#现有1 5 10 20 50 100等6种面额票子，任意S,求最少张的票子组合
#S=sum x_i*a_i 使得 f=sum x_i 最小
#初值 f(1)=f(5)=f(10)=f(20)=f(50)=f(100)=1
S=int(input())
A=[1,5,10,20,50,100]
f=[0 for i in range(S+1)]
minnn=100000 #最大初值
for i in range(1,S+1):
if i in A:
f[i]=1
continue
minn=minnn
for j in A:
if i-j>0:
minn=min(f[i-j],minn)
f[i]=minn+1
print(f[S])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#动态规划平方个数最小问题
#n=sum(x_i^2),i=1,2,...,n 求最小n
#12=4+4+4 n=3
n=13
f=[0 for i in range(n+1)]
for i in range(n+1):
minn=i
j=1
while j*j<=i:
minn=min(f[i-j*j]+1,minn)
j+=1
f[i]=minn
print(f[n])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#动态规划之最长回文串
#p[i:j]的子问题是p[i+1:j-1]
s='abba'
s=list(s)
n=len(s)
maxlen=1
start=0
f=[[False for i in range(n)] for j in range(n)]
#初始化，
for i in range(n):
f[i][i]=True
if i<n-1 and s[i]==s[i+1]:
f[i][i+1]=True
start=i
maxlen=2
for k in range(3,n+1):
for i in range(n-k):
j=i+k-1
if f[i+1][j-1] and s[i]==s[j]:
f[i][j]=True
maxlen=k
start=i
print(''.join(s[start-1:(start+maxlen+1)]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#动态规划之最长递增序列
l=[2,3,5,2,6]
n=len(l)
f=[0 for i in range(n)]
for i in range(n):
f[i]=1
for j in range(i):
if l[i]>l[j] and f[j]+1>f[i]:
f[i]=f[j]+1
max_l=f[0]
for i in range(n):
if f[i]>max_l:
max_l=f[i]
print(max_l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#楼层扔珠子问题
#某楼有100层。你手里有两颗玻璃珠。
#当你拿着玻璃珠在某一层往下扔，一定会有两个结果，玻璃珠碎了或者没碎。
#这幢大楼有个临界楼层。低于楼层，玻璃珠不会碎，等于或高于，玻璃珠一定会碎。
#玻璃珠碎了就不能再扔。
#现在让你设计一种方式，使得在该方式下，最坏的情况扔的次数最少。
#例如：第一次选择在60层扔，
#若碎了，说明临界点在60层及以下楼层，
#这时只有一颗珠子，剩下的只能是从第一层，一层一层往上实验，
#最坏的情况，要实验59次，加上之前的第一次，一共60次。
#若没碎，则只要从61层往上试即可，最多只要试40次，加上之前一共需41次。
#两种情况取最多的那种。故这种方式最坏的情况要试60次。
n=100 #100层
f=[0 for i in range(101)]
for i in range(2,n+1):
f[i]=i
for j in range(i):
f[i]=min(f[i],max(j,1+f[i-j]))
print(f[n])
