27373: 最大整数

http://cs101.openjudge.cn/practice/27373

假设有n个正整数，要求从中选取几个组成一个位数不超过m的新正整数，现需要求出最大可能数值是多少。

比如有4个数，993，923，3817，3807，组成新数不超过7位，那么新数最大值为9933817。

输入

第一行m表示新数的最大位数，m<=200。第二行n表示整数的数量，n <= 1000。接下来一行有n个整数，每个整数的位数不超过20。

输出

输出为一行，为这n个正整数能组成的不超过m位的最大整数值。

样例输入

Sample1 Input:
4
4
23 9 182 79

Sample1 Output:
9182

样例输出

Sample2 Input:
5
4
8 765 43 21

Sample2 Output:
84321

提示

tags: dp，greedy，string，sort

来源：2023fall pyn

卢卓然，23级生命科学学院

思路：这道题的tag很对，dp, greedy, string, sort都有成分，是非常综合、非常好、当然也非常难的一道题。

首先关于bubble sort和string的成分，是这道题中的“最大整数”模型。要做此题，要先明白这个模型：给定一个序列，输出这些数字随意拼接所能产生的最大整数。借助冒泡排序实现这一点。

python

for i in range(n):
    for j in range(n-1-i):
        if l[j] + l[j+1] > l[j+1] + l[j]:
            l[j],l[j+1] = l[j+1],l[j]

然后，关于dp的部分，是0-1背包的变形。dp[i][j]状态定义为在l的前i个数中随意选择，满足拼凑起来不超过j位，得到的整数的最大可能数值。那么dp[n][m]即为所求。

接着，dp数组的建立，dp数组初始化最好用''，也就是空字符串。因为如果用0，会把0看作数字后续操作中进行拼接，这显然是不对的。

dp状态转移方程。如果weight[i-1]>j，说明不能选第i个数字，否则会超位数。否则，可以选第i个也可以不选。这时需要取选第i个和不选第i个的更大的值。对于不选第i个的情况，很好理解，就是dp[i-1][j]。而对于选第i个的情况，为什么是int(l[i-1]+dp[i-1][j-weight[i-1]])就需要解释一下了。

对列表l进行排序后，结果是对任意两个相邻的字符串型的数字，i+j<j+i。但是这样的排序，能否保证对于这个列表的任意一个子列，其顺序是这个子列中数字所组成的最大整数呢？

from 23 元培 夏天明
是的，因为不难验证由i+j≤j+i所定义的i与j的关系i€j满足：
1）若i€j，j€k，则i€k
2）对任意的i，i€i
3）若i€j，j€i，则i=j
4）对任意的i，j，都有i€j和j€i至少成立一个
这意味着€是全序，所以由冒泡排序原理知道，可以将整个列表排成有序列.

所以，l是一个全序集。那么对于选第i个数的情况，根据0-1背包的思路，需要找到“前i-1个数里，拼接后总位数不超过[j-weight[i]]的数字组合”，这些数字组合里的数和第j个数一起构成数字组合。因为l是一个全序集，所以要想保证值最大，就还需要这些数按照l中的相对位置的相反顺序进行排布，也就是说，第i个数的位置一定在前i-1个数的数字组合之前，也就是在i个数的整体数字组合的最前面。所以前i-1个数的数字组合仍然是挨在一起的。而这些前i-1个数的数字组合中，值最大的那个就是dp[i-1][j-weight[i]]对应的数字组合。所以才有这样的递推关系，这个分析过程也可以看作是一种greedy。

至此，代码的主要逻辑都已分析完毕。代码开头的函数f是为了处理dp数组中空字符串不能转化为整型的问题。

python

def f(string):
    if string=='':
        return 0
    else:
        return int(string)
m=int(input())#最大位数
n=int(input())#正整数数量
l=input().split()
#冒泡排序
for i in range(n):
    for j in range(n-1-i):
        if l[j] + l[j+1] > l[j+1] + l[j]:
            l[j],l[j+1] = l[j+1],l[j]
weight=[]#每个元素的位数
for num in l:
    weight.append(len(num))
#dp[i][j]在前i数中选择，不超过j位，最大可能数值
dp=[['']*(m+1) for _ in range(n+1)]
for k in range(m+1):
    dp[0][k]=''#无法组成整数
for q in range(n+1):
    dp[q][0]=''#无法组成整数
for i in range(1,n+1):
    for j in range(1,m+1):
        if weight[i-1]>j:#不能选第i个，因为会超位数
            dp[i][j]=dp[i-1][j]
        else:#可以选第i个也可以不选
                dp[i][j]=str(max(f(dp[i-1][j]),int(l[i-1]+dp[i-1][j-weight[i-1]])))
print(dp[n][m])

思路：先对数据进行预处理，再进行dp，由于一个数只能用一次，所以添加了一个temp来缓存。可以用滚动数组反向更新优化temp。

python

# 谭宇睿 工学院
limit = int(input())
n = int(input())
lst = list(map(str, input().split()))


def sorting(a, b):
    if int(a + b) > int(b + a):
        return True
    else:
        return False


for i in range(n):
    for j in range(i, n):
        if not sorting(lst[i], lst[j]):
            lst[i], lst[j] = lst[j], lst[i]

dp = [0] * (limit + 1)  # dp[i]表示i位数时最大值
temp = [0] * (limit + 1)
for j in lst:
    for i in range(len(j), limit + 1):
        dp[i] = max(dp[i], int(str(temp[i - len(j)]) + j))
    temp[:] = dp
print(dp[limit])

上面谭宇睿同学的代码是一个关于“拼接数字”问题的求解，目的是找出一个给定长度 limit 的最大拼接数字。这个问题涉及到排序和动态规划，目标是通过给定的数字列表拼接出一个最大值。

问题分析

排序：通过将数字按某种规则排序，使得拼接后的结果最大。
动态规划：用 dp[i] 表示拼接出长度为 i 的最大值，通过动态更新来填充 dp 数组。

优化点

排序优化：当前的排序使用了 sorting(a, b) 函数，这会比较每一对数字 a 和 b 的拼接结果。直接使用 Python 的 sorted 和自定义排序函数可以避免额外的嵌套循环。
动态规划的优化：目前的 dp 更新方式通过数组 temp 复制，效率较低。可以直接使用 dp 数组来减少空间消耗并优化性能。
避免重复操作：sorting(a, b) 是基于 a + b 和 b + a 来做比较，Python 的内置排序可以通过 key 来实现，这样可以直接使用。

代码优化

python

import math
limit = int(input())
n = int(input())
lst = list(map(str, input().split()))

# 两倍长度是正确的。
max_len = len(max(lst, key = lambda x:len(x)))
lst.sort(key = lambda x: x * math.ceil(2*max_len/len(x)), reverse = True)


# 动态规划部分优化
dp = [0] * (limit + 1)  # dp[i]表示长度为i的最大拼接值
for num in lst:
    for i in range(limit, len(num) - 1, -1):  # 反向更新，避免重复计算
        dp[i] = max(dp[i], dp[i - len(num)] * (10 ** len(num)) + int(num))

print(dp[limit])

代码解析
排序部分优化：
使用 x*math.ceil(2*max_len/len(x)) 来模拟比较拼接后的字符串，这样能够避免自定义的排序函数，提高了代码简洁性和效率。使得字符串扩展成一个更长的形式，确保通过这种扩展后，排序结果是正确的。
动态规划部分优化：
直接在 dp 数组中进行更新，避免使用额外的 temp 数组。
采用反向更新的方法：从 limit 倒推到 len(num)，这样可以保证每个数字只参与一次计算。
时间复杂度分析
排序部分：使用 sorted 进行排序，时间复杂度是 $O (n \log n)$ ，其中 n 是数字个数。由于每个数字被扩展成一个较长的字符串（最多 10 位），实际上比较的时间复杂度为 $O (n \log n)$ 。
动态规划部分：对于每个数字，更新 dp 数组最多需要遍历 limit 次，因此时间复杂度是 $O (n \times l i m i t)$ 。
所以，整体时间复杂度是 $O (n \log n + n \times l i m i t)$ ，其中 n 是数字个数，limit 是目标拼接的最大长度。

【戴德音】一定要排序吗，感觉dp可以直接找最大的数值，像背包问题一样？

【陈俊逸】在考虑第三个数的时候不能确定插在前面中间还是末尾合适。比如，要组成一个很长的数，但是我给你的数都是个位数，而且是无序的。那你肯定得先把9排到前面，然后再去排小的数字。排一遍序，就保证了我后面考虑的数一定是放在最前面或者最后面，能确保这个解是最大的，所以他要提前排个序。

什么是“无后效性”？无后效性是动态规划问题的一条重要性质，具体指的是：

当前状态的最优解只依赖于之前的状态，而与未来如何决策无关。 换句话说，当前决策一旦做出，不会影响未来阶段的最优性。这种性质确保了动态规划可以通过分阶段最优递推全局最优解。

27373: 最大整数。http://cs101.openjudge.cn/practice/27373排序是确保无后效性成立的前提：

排序可以将问题转化为“选择数字拼接”的问题，消除了后续顺序对当前决策的影响。
如果不排序，未来的拼接顺序会影响当前状态，动态规划的无后效性将被破坏。

dp[j]表示能凑到j位数的字符串中这个多位数最大的那个构造（不存在则为某个自定初值）。注意如果j位是可以构造的，那么构造所用的顺序一定是按照A+B>B+A排序好的顺序才使得数最大（之前作业题），故做dp前要先这样排序再做。最后位数从大到小即可。

python

from functools import cmp_to_key
def cmp(x, y): # -1:不交换，x在y前；1:交换，y在x前
    if x + y > y + x: return -1
    return 1
m = int(input())
n = int(input())
s = input().split()
s = sorted(s, key = cmp_to_key(cmp))
ans = [""] + ["!"] * m
for i in range(n):
    for j in range(m, len(s[i]) - 1, -1):
        if ans[j - len(s[i])] != "!":
            if ans[j] == "!" or ans[j - len(s[i])] + s[i] > ans[j]: ans[j] = ans[j - len(s[i])] + s[i]
for j in range(m, -1, -1):
    if ans[j] != "!":
        print(ans[j])
        break

python

m = int(input())
n = int(input())
arr = list(input().split())
arr.sort(key=lambda x: int(x)/(10**len(x)-1), reverse=True)
dp = [0]*(m+1)
for number in arr:
    for j in range(m, len(number)-1, -1):
        if dp[j-len(number)] == 0:
            dp[j] = max(dp[j], int(number))
        else:
            dp[j] = max(dp[j], int(str(dp[j-len(number)])+number))

print(dp[m])

27373: 最大整数 ​

27373: 最大整数