得物秋招 2023.11.15 编程题目与题解

发表于 2023-11-23 分类于笔试阅读次数：本文字数： 1.6k 阅读时长 ≈ 1 分钟

1、最少数字

小明用计算机随机生成了$N$个正整数，他希望从这$N$个数中选取若干个数，使得它们的和等于$M$。这些随机生成的数字可能会相同，但是每个数字最多只允许使用一次。

当然这样的选取方案可能不存在，也可能有多个。

现在希望你编写一个程序，能够找出数字个数最少的选取方案，输出对应的最少数字的个数，如果无解输出"No solution"。

输入

单组输入，每组输入$2$行。

第$1$行包合两个正整数$N$和$M$，分别表示初始输入的正整数个数和目标数字和。

$(N\le 10^3,M\le 10^5)$

第$2$行为$N$个正整数，两两之甸用空格隔开(每一个正整数均小于等于$10^5$)。

输出

输出数字个数最少的选取方案中所包含的最少数字个数，如果无解输出"No solution"。

样例

输入：
5 5
1 3 2 1 1

输出：
2

解答

这是一道经典的01背包问题。将数的和视为物品的重量，其价值视为$1$，那么我们此时是希望最小化价值之和。令$a_i$表示第$i$个输入的数，$f(i,j)(0\le i\le n,0\le j\le m)$表示在前$i$个数中，和为$j$的最小子集的大小。那么不难写出如下状态转移方程：

\[f(i,j)= \left \{\begin{aligned} &0 & & \text{if}\quad i=0\land j=0 \\ &+\infty & & \text{if}\quad i=0\land j>0 \\ &f(i-1,j) & & \text{if}\quad i>0\land j<a_i \\ &\min\{f(i-1,j),f(i-1,j-a_i)+1\} & & \text{if}\quad i>0\land j\ge a_i \\ \end{aligned}\right.\]

其中，方程的第$4$行表示了两种不同的选择：如果不选择$a_i$，那么元素之和不变，因此从$f(i-1,j)$转移过来；如果选择了元素$a_i$，那么元素之和将增加$a_i$，因此从$f(i-1,j-a_i)$转移过来，并多计算一个元素个数。

因此最终答案为$f(n,m)$。如果$f(n,m)=+\infty$，那么说明无解。

代码

n, m = map(int, input().split())
a = list(map(int, input().split()))
inf = 10 ** 9
f = [inf for _ in range(m + 1)]
f[0] = 0
for x in a:
    for i in range(m, x - 1, -1):
        f[i] = min(f[i], f[i - x] + 1)
print(f[m] if f[m] != inf else "No solution")

2、搭建电路

小明迷上了一个搭建电路的游戏。

在游戏中，两个电子元件之间只能存在唯一通路，每次在两个电子元件之间增加一条有效电路(两个元件之间先前没有电路相连) 都将获得相应的积分奖励。 (初始状态时电子元件之间均未连接)。

已知电子元件数量$n$和部分电子元件之间的奖励积分值，如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

输入

第$1$行输入两个正整数$n$和$m$，其中$n$表示电子元件数量$(n<=100)$，$m$表示提供了$m$对电子元件之间的奖励积分值$(m<=1000)$。两个正整数之间用空格隔开。

第$2$行到第$m+1$行对应$m$对电子元件及其对应的奖励积分值，每一行包含三个正整数，第$1$个和第$2$个整数表示电子元件编号($从$1开始)，第$3$个整数表示两个元件之间搭建电路的奖励积分$num(0<num<10^9)$。整数之同用空格隔开。

输出

输出占$1$行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出"No solution." (注意，tion后有英文句号)。

样例

解答

本题是最大生成树的模板题。相比于最小生成树，只需要从大到小遍历所有边，并尝试添加即可，这个过程使用Kruskal算法可以解决。

代码

n, m = map(int, input().split())
e = []
for _ in range(m):
    e.append(list(map(int, input().split())))
e.sort(key=lambda x: -x[2])
fa = list(range(n + 1))


def find(x):
    if fa[x] == x:
        return fa[x]
    fa[x] = find(fa[x])
    return fa[x]


def merge(x, y):
    fa[find(x)] = find(y)


cnt = ans = 0
for u, v, w in e:
    if find(u) != find(v):
        merge(u, v)
        ans += w
        cnt += 1
print(ans if cnt == n - 1 else "No solution.")