HNUCM-OJ-2023年春季学期《算法分析与设计》练习10

问题 A: 最长递增子序列

题目描述

给出一个序列a1,a2,a3,a4,a5,a6,a7...an，求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质：s1<s2<s3<...<sn并且这个子序列的长度最长。输出这个最长子序列的长度，要求时间复杂度为O(n2)。

输入

每组输入包括两行，第一行为序列长度n，第二行为序列。

输出

输出最长递增子序列的长度。

样例输入 Copy

7
1 7 3 5 9 4 8

样例输出 Copy

4

思路：动态规划问题，b数组b[i]表示a[i]的最长子序列长度，然后输出max(b);

两种方法。

while True:
    n=int(input())
    a = list(map(int,input().split()))
    b=[1]*n
    for i in range(n):
        maxlen=0
        for j in range(i-1,-1,-1):
            if a[i]>a[j] and b[j]>maxlen:
                maxlen=b[j]
        b[i]=maxlen+1
    print(max(b))

while True:
    def LIS(array):
        n = len(array)
        lis = [0]*n
        for i in range(n):
            lis[i] = 1
            for j in range(i):
                if array[i]>array[j] and lis[j]+1>lis[i]:
                    lis[i] = lis[j]+1
        return max(lis)
    n=int(input())
    a = list(map(int,input().split()))
    print(LIS(a))

问题 B: 构造最长递增子序列

7
1 7 3 4 9 2 3

1 3 4 9

while True:
    def LIS(array):
        n = len(array)
        lis = [0]*n
        m=[-1]*n
        result=[0]*n
        for i in range(n):
            lis[i] = 1
            for j in range(i):
                if array[i]>array[j] and lis[j]+1>lis[i]:
                    lis[i] = lis[j]+1
                    m[i]=j
        k=max(lis)
        index=lis.index(k)
        result=[0]*k
        while k>0:
            result[k-1]=a[index]
            k-=1
            index=m[index]
        return result
    n=int(input())
    a = list(map(int,input().split()))
    print(*(LIS(a)))

问题 C: 出列人数

题目描述

有N位同学站在一排，体育老师要请其中的(N-K)位同学出列，将剩下的K位同学从左到右依次编号为1,2,3,…K，他们的身高分别为T1,T2,T3,…TK，要求满足T1<T2<T3<…<TK。已知N位同学的身高，请设计一个算法，计算最少需要几位同学出列可使得剩下的同学满足上述要求。

输入

多组输入，对于每一组测试数据，第1行N表示同学数量（n<=1000)。
第2行包含N个正整数，分别表示每一个同学的身高。（单位：厘米）

输出

输出最少需要出列的同学人数。

样例输入 Copy

4
172 185 169 178
5
165 168 174 170 182

样例输出 Copy

2
1

思路：只需要n-max(lis)即可

while True:
    def LIS(array):
        n = len(array)
        lis = [0]*n
        for i in range(n):
            lis[i] = 1
            for j in range(i):
                if array[i]>array[j] and lis[j]+1>lis[i]:
                    lis[i] = lis[j]+1
        return max(lis)
    n=int(input())
    a = list(map(int,input().split()))
    print(n-LIS(a))

问题 D: 0-1背包问题

题目描述

给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为C。如何选择装入背包的物品，可以使得装入背包中物品的总价值最大？

输入

每组输入包括三行，
第一行包括物品个数n，以及背包容量C。
第二、三行包括两个一维数组，分别为每一种物品的价值和重量。

输出

输出包括两行，第一行为背包的最大总价值，第二行为所选取的物品。
例如：最大总价值=15，物品选取策略为11001。数据保证答案唯一。

样例输入 Copy

5 10
6 3 5 4 6
2 2 6 5 4

样例输出 Copy

15
11001

思路：典型的01背包问题，二维数组保存最大值，

def max_():
    jmax=min(w[n-1]-1,c)
    for j in range(jmax+1):
        f[n-1][j]=0
    for j in range(w[n-1],c+1):
        f[n-1][j]=v[n-1]
    for i in range(n-1,-1,-1):
        jmax=min(w[i]-1,c)
        for j in range(jmax+1):
            f[i][j] = f[i+1][j]  
        for j in range(w[i],c+1):
            f[i][j] = max(f[i+1][j], f[i+1][j-w[i]] + v[i])
def tr(c):
    for i in range(n):
        if f[i][c]==f[i+1][c]:
            result[i]=0
        else:
            result[i]=1
            c-=w[i]
        result[n]=1 if f[n][c]>0 else 0             
n,c=map(int,input().split())
v=list(map(int,input().split()))
w=list(map(int,input().split()))
result=[0]*(n+1)
f = [[0] * (c + 1) for _ in range(n + 1)]
max_()
tr(c)
print(f[0][c])
for i in range(n):
    print(result[i],end='')

问题 E: XP的午餐

题目描述

XP每天都会思考一个问题，今天午餐去哪里吃？这是一个很重要的问题，这会影响到他下午的体力值。他的午餐预算是M元，现在有N种菜品，每一种菜品的价格和能够提供的体力值已知（每种菜品只能选择一次），请问如何选择菜品能够让XP下午的体力值最大呢？

输入

多组输入
第一行：M元和菜品数量N。
接下来N行，每一行两个整数，分别表示每一种菜品的价格(vi)和能够获得的体力值(wi)。
（0<N<=20,0<=M<=1000）(0<=vi<=50，0<=wi<=100)

输出

最大体力值。

样例输入 Copy

10 5
1 5
2 4
3 3
4 2
5 1

样例输出 Copy

14

思路：同理01背包问题，其实二维数组可以优化为一维数组，代码变得更加简单，大家可以参考！

def max_():
    jmax=min(w[n-1]-1,c)
    for j in range(jmax+1):
        f[n-1][j]=0
    for j in range(w[n-1],c+1):
        f[n-1][j]=v[n-1]
    for i in range(n-1,-1,-1):
        jmax=min(w[i]-1,c)
        for j in range(jmax+1):
            f[i][j] = f[i+1][j]  
        for j in range(w[i],c+1):
            f[i][j] = max(f[i+1][j], f[i+1][j-w[i]] + v[i])
while True:
    c,n=map(int,input().split())
    v=[]
    w=[]
    f = [[0] * (c + 1) for _ in range(n + 1)]
    for i in range(n):
        wi,vi=map(int,input().split())
        w.append(wi)
        v.append(vi)
    max_()
    print(f[0][c])

优化的代码

while True:
    c, N= map(int, input().split()) 
    w = [0] * (N + 1)  
    v = [0] * (N + 1)  
    for i in range(1, N + 1):
        w[i], v[i] = map(int, input().split())
    f = [0 for i in range(c+1)]  
    for i in range(1, N + 1):
        for j in range(c,w[i]-1,-1):
            f[j] = max(f[j], f[j - w[i]] + v[i])
    print(f[c])

问题 F: 补充能量

题目描述

一年一度的宇宙超级运动会在宇宙奥特英雄体育场隆重举行。X星人为这场运动会准备了很长时间，他大显身手的时刻终于到了！
为了保持良好的竞技状态和充沛的体能，X星人准备了N个不同的能量包，每个能量包都有一个重量值和能量值。由于这些能量包的特殊性，必须要完整地使用一个能量包才能够发挥功效，否则将失去能量值。
考虑到竞赛的公平性，竞赛组委会规定每个人赛前补充的能量包的总重量不能超过W。
现在需要你编写一个程序计算出X星人能够拥有的最大能量值是多少？

输入

单组输入。
第1行包含两个正整数N和W，其中N<=$10^3$，W<=$10^3$。
第2行包含N个正整数，分别表示每一个能量包的重量，两两之间用空格隔开。
第3行包含N个正整数，分别表示每一个能量包的能量值，两两之间用空格隔开。

输出

输出X星人能够拥有的最大能量值。

样例输入 Copy

3 10
4 5 7
100 120 200

样例输出 Copy

220

def max_():
    jmax=min(w[n-1]-1,c)
    for j in range(jmax+1):
        f[n-1][j]=0
    for j in range(w[n-1],c+1):
        f[n-1][j]=v[n-1]
    for i in range(n-1,-1,-1):
        jmax=min(w[i]-1,c)
        for j in range(jmax+1):
            f[i][j] = f[i+1][j]  
        for j in range(w[i],c+1):
            f[i][j] = max(f[i+1][j], f[i+1][j-w[i]] + v[i])
n,c=map(int,input().split())
w=list(map(int,input().split()))
v=list(map(int,input().split()))
f = [[0] * (c + 1) for _ in range(n + 1)]
max_()
print(f[0][c])

优化版

n,c=map(int,input().split())
w=list(map(int,input().split()))
w.insert(0,0)
v=list(map(int,input().split()))
v.insert(0,0)
dp=[0]*(c+1)
for i in range(1,n+1):
    for j in range(c,w[i]-1,-1):
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
print(dp[c])

问题 G: 道具的魅力值

题目描述

在某网络游戏中提供了一个道具库，在道具库中每种道具均有若干件（数量已知），游戏玩家购买一件道具将获得一定的魅力值。
已知每种道具的价格和魅力值，请编写一个程序，在总价格不超过某个上限的情况下使得所购道具的魅力值之和达到最大。

输入

每组测试数据的输入有n+1行，n表示道具的种类。（n<=100，p<=10000）
第1行包含两个正整数，分别表示道具种类数n和总价值的上限p，两个数字之间用空格隔开。
第2行到第n+1行分别对应于第1种道具到第n种道具的信息，每1行包含三个正整数，两个数字之间用空格隔开，三个正整数分别表示某一种道具的数量、单个道具的价格和魅力值。

输出

每组测试数据的输出只有一行，即道具魅力值的最大和。

样例输入 Copy

3 10
2 2 3
1 5 10
2 4 12

样例输出 Copy

27

思路：这是多重背包问题，第一种可以转换为01背包问题，但复杂度比较大，内存容易超限。第二种写状态转移方程式

def max_():
    jmax=min(w[n-1]-1,c)
    for j in range(jmax+1):
        f[n-1][j]=0
    for j in range(w[n-1],c+1):
        f[n-1][j]=v[n-1]
    for i in range(n-1,-1,-1):
        jmax=min(w[i]-1,c)
        for j in range(jmax+1):
            f[i][j] = f[i+1][j]  
        for j in range(w[i],c+1):
            f[i][j] = max(f[i+1][j], f[i+1][j-w[i]] + v[i])
while True:
    m,c=map(int,input().split())
    w,v=[],[]
    n=0
    for i in range(m):
        x,y,z=map(int,input().split())
        n+=x
        for j in range(x):
            w.append(y)
            v.append(z)
    f = [[0] * (c + 1) for _ in range(n + 1)]
    max_()
    print(f[0][c])

while True:
    n,p=map(int,input().split())
    num,prices,val=[],[],[]
    dp=[0]*(p+1)
    num.append(0),prices.append(0),val.append(0)
    for i in range(n):
        x,y,z=map(int,input().split())
        num.append(x),prices.append(y),val.append(z)
    for i in range(1,n+1):
        for j in range(p,prices[i]-1,-1):
            for k in range(1,min(num[i],j//prices[i])+1):
                dp[j]=max(dp[j],dp[j-k*prices[i]]+k*val[i])
    print(dp[p])