DP经典问题的python实现

程序员文章站 2022-03-11 14:50:49

title: DP经典问题的python实现date: 2020-03-26 22:13:26categories: 算法tags: [python, DP]01背包有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。输入格式第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分....

title: DP经典问题的python实现
date: 2020-03-26 22:13:26
categories: 算法
tags: [python, DP]

01背包

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

输出样例：

普通代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[[0 for i in range(0,m+1)] for i in range(0,n+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(0,m+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])

print(dp[n-1][m])

优化代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[0 for i in range(0,m+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(m,v[i]-1,-1):
        dp[j]=max(dp[j],dp[j-v[i]]+w[i])

print(dp[m])

完全背包

有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 ii 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 ii 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

输出样例：

基本代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[[0 for i in range(0,m+1)] for i in range(0,n+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(0,m+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:
            dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
print(dp[n-1][m])

优化代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[0 for i in range(0,m+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(v[i],m+1):
            dp[j]=max(dp[j],dp[j-v[i]]+w[i])
print(dp[m])

石子合并

设有N堆石子排成一排，其编号为1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有4堆石子分别为 1 3 5 2，我们可以先合并1、2堆，代价为4，得到4 5 2，又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；

如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

输入格式

第一行一个数N表示石子的堆数N。

第二行N个数，表示每堆石子的质量(均不超过1000)。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤N≤3001≤N≤300

输入样例：

4
1 3 5 2

输出样例：

代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n=int(input())
a=list(IA())

s=[0 for i in range(0,n+1)]

dp=[[0 for i in range(0,n+1)] for i in range(0,n+1)]

s[0]=0
for i in range(0,n):
    s[i+1]=s[i+1-1]+a[i]
    

for le in range(2,n+1):
    for i in range(1,n+1):
        j=i+le-1
        if j>n:break
        dp[i][j]=1e18
        for k in range(i,j):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1])
            
print(dp[1][n])

最长公共子序列

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数N和M。

第二行包含一个长度为N的字符串，表示字符串A。

第三行包含一个长度为M的字符串，表示字符串B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001≤N≤1000,

输入样例：

4 5
acbd
abedc

输出样例：

代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=IA()
s1=str(input())
s2=str(input())

dp=[[0 for i in range(0,m+1)] for i in range(0,n+1)]

for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if s1[i-1]==s2[j-1]:
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)
            
            
print(dp[n][m])

最长上升子序列

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N≤10001≤N≤1000，
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

代码

o(n^2)

IA=lambda:map(int,input().split())

n=int(input())
a=list(IA())

dp=[0 for i in range(0,n)]

ans=0

for i in range(0,n):
    
    dp[i]=1
    for j in range(0,i):
        if a[i]>a[j]:
            dp[i]=max(dp[i],dp[j]+1)
  
    ans=max(dp[i],ans)

print(ans)

O(n*logn)

IA=lambda:map(int,input().split())

n=int(input())
a=list(IA())

dp=[0 for i in range(0,n)]

def two_find(l,r,val):
    while l<r:
        mid=l+r>>1
        if dp[mid]>=val:
            r=mid
        else:
            l=mid+1
    return r
cnt=0
dp[cnt]=a[0]
cnt+=1
for i in range(1,n):
    if a[i]>dp[cnt-1]:
        dp[cnt]=a[i]
        cnt+=1
    else:
        dp[two_find(0,cnt,a[i])]=a[i]

print(cnt)

摘花生

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

DP经典问题的python实现

输入格式

第一行是一个整数T，代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。

数据范围

1≤T≤100
1≤R,C≤100
0≤M≤10000≤M≤1000

输入样例：

输出样例：

8
16

代码

朴素做法


IA=lambda:map(int,input().split())

T=int(input())


for t in range(0,T):
    n,m=IA()
    mp=[[0 for j in range(0,m+1)] for i in range(0,n+1)]
    dp=[[0 for j in range(0,m+1)] for i in range(0,n+1)]

    for i in range(1,n+1):
        mp[i][1:]=list(IA())
    
    #print(mp)
    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+mp[i][j]
    print(dp[n][m])

等价变化的优化(删掉一维是否可行)


IA=lambda:map(int,input().split())

T=int(input())


for t in range(0,T):
    n,m=IA()
    mp=[[0 for j in range(0,m+1)] for i in range(0,n+1)]
    dp=[0 for j in range(0,m+1)]

    for i in range(1,n+1):
        mp[i][1:]=list(IA())
    
    #print(mp)
    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[j]=max(dp[j],dp[j-1])+mp[i][j]
    print(dp[m])

地宫取宝

X 国王有一个地宫宝库，是 n×mn×m 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 kk 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 kk 件宝贝。

输入格式

第一行 33 个整数，n,m,kn,m,k，含义见题目描述。

接下来 nn 行，每行有 mm 个整数 CiCi 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 kk 个宝贝的行动方案数。

该数字可能很大，输出它对 10000000071000000007 取模的结果。

数据范围

1≤n,m≤501≤n,m≤50,
1≤k≤121≤k≤12,
0≤Ci≤120≤Ci≤12

输入样例1：

2 2 2
1 2
2 1

输出样例1：

输入样例2：

2 3 2
1 2 3
2 1 5

输出样例2：

代码

# 最长上升子序列和摘花生的原题
IA=lambda:map(int,input().split())
n,m,k=IA()
C=13
MOD=1000000007

w=[[0 for j in range(0,m+1)] for i in range(0,n+1)]

dp=[[[[0 for y in range(C+1)] for x in range(k+1)] for j in range(m+1)] for i in range(n+1)]

for i in range(1,n+1):
    w[i][1:]=list(IA())
    for j in range(1,m+1):
        w[i][j]+=1
    

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

for i in range(1,n+1):
    for j in range(1,m+1):
        if i==1 and j==1:continue
        for x in range(0,k+1):
            for y in range(0,C+1):
                dp[i][j][x][y]=(dp[i][j][x][y]+dp[i-1][j][x][y])%MOD
                dp[i][j][x][y]=(dp[i][j-1][x][y]+dp[i][j][x][y])%MOD
                if w[i][j]==y and x>0:
                    for t in range(0,y):
                        dp[i][j][x][y]=(dp[i-1][j][x-1][t]+dp[i][j][x][y])%MOD
                        dp[i][j][x][y]=(dp[i][j-1][x-1][t]+dp[i][j][x][y])%MOD
ans=0
for i in range(0,C+1):
    ans=(ans+dp[n][m][k][i])%MOD

print(ans)

波动数列

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为 nn 和为 ss 而且后一项总是比前一项增加 aa 或者减少 bb 的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数 n,s,a,bn,s,a,b，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 100000007100000007 的余数。

数据范围

1≤n≤10001≤n≤1000,
−109≤s≤109−109≤s≤109,
1≤a,b≤1061≤a,b≤106

输入样例：

4 10 2 3

输出样例：

样例解释

两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

代码

IA=lambda:map(int,input().split())
def get_mod(a,b):
    return (a%b+b)%b

MOD=100000007  
n,s,a,b=IA()
dp=[[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0]=1
for i in range(1,n):
    for j in range(0,n):
        dp[i][j]=(dp[i-1][get_mod(j-(n-i)*a,n)]+dp[i-1][get_mod(j+(n-i)*b,n)])%MOD
print(dp[n-1][get_mod(s,n)])

本文地址：https://blog.csdn.net/sdz20172133/article/details/109217473

相关标签：算法回顾 # DP 算法 python

上一篇： AE数字校色曲线怎么用？AE简单调色RGB与其对抗色的教程

下一篇：一名即将大三的在校菜鸡程序员的复盘

DP经典问题的python实现

title: DP经典问题的python实现 date: 2020-03-26 22:13:26 categories: 算法 tags: [python, DP]

01背包

输入格式

输出格式

数据范围

输入样例

输出样例：

普通代码

优化代码

完全背包

输入格式

输出格式

数据范围

输入样例

输出样例：

基本代码

优化代码

石子合并

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

最长公共子序列

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

最长上升子序列

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

摘花生

输入格式

输出格式

数据范围

输入样例：

输出样例：

代码

地宫取宝

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

代码

波动数列

输入格式

输出格式

数据范围

输入样例：

输出样例：

样例解释

代码

Python实现字典(dict)的迭代操作示例

Python实现迭代时使用索引的方法示例

Python numpy实现二维数组和一维数组拼接的方法

几种经典排序算法的JS实现方法

Python实现快速多线程ping的方法

python实现判断数组是否包含指定元素的方法

Python实现将目录中TXT合并成一个大TXT文件的方法

完美解决Python matplotlib绘图时汉字显示不正常的问题

解决python中画图时x,y轴名称出现中文乱码的问题

Python实现点阵字体读取与转换的方法

title: DP经典问题的python实现
date: 2020-03-26 22:13:26
categories: 算法
tags: [python, DP]