分割等和子集思想做的

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int target, n;
    cin >> target >> n;
    vector<int> a(n);
    
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    // 如果接口板总转发能力不等于2 * target，无法分成两组
    if (target * 2 != sum) {
        cout << -1 << endl;
        return 0;
    }

    // 动态规划数组 dp，dp[j] 表示是否可以用接口板凑出转发能力为 j 的组
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    vector<vector<int>> path(n + 1, vector<int>(target + 1, -1));  // 用于记录路径
    dp[0][0] = true;  // 初始条件：0块板子凑出0的转发能力

    // 开始 01 背包动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = target; j >= a[i - 1]; j--) {
            if (dp[i - 1][j - a[i - 1]]) {
                dp[i][j] = true;
                path[i][j] = j - a[i - 1];  // 记录是从哪里转移过来的
            }
        }
        for (int j = 0; j <= target; j++) {
            if (!dp[i][j] && dp[i - 1][j]) {
                dp[i][j] = true;
            }
        }
    }

    // 如果无法凑出目标转发能力 target，返回 -1
    if (!dp[n][target]) {
        cout << -1 << endl;
        return 0;
    }

    // 回溯，找到其中一个解
    vector<int> group1, group2;
    int rem = target;
    for (int i = n; i > 0; i--) {
        if (path[i][rem] != -1) {  // 表示接口板 a[i-1] 被选中
            group1.push_back(a[i - 1]);
            rem -= a[i - 1];
        } else {
            group2.push_back(a[i - 1]);
        }
    }

    // 排序输出结果，按题目要求排序
    sort(group1.begin(), group1.end());
    sort(group2.begin(), group2.end());

    if (group1[0] < group2[0] || (group1[0] == group2[0] && group1.size() > group2.size())) {
        for (int i : group1) cout << i << " ";
        cout << endl;
        for (int i : group2) cout << i << " ";
    } else {
        for (int i : group2) cout << i << " ";
        cout << endl;
        for (int i : group1) cout << i << " ";
    }

    return 0;
}

题面描述:

塔子哥在进行计网实验后，又收到了一周的接口板需求。他需要为两台设备配置接口板，使得每台设备的接口板转发能力之和恰好等于设备的整机转发能力。输入包括目标设备的转发能力、客户订购的接口板数量以及接口板的转发能力列表。若能够满足条件，输出两台设备配置的接口板转发能力列表（需按从小到大排列）；若无法满足，则输出-1。

思路

由于题目保证如果存在解，那么解一定是唯一的，所以接口板容量之和肯定是整机转发能力的两倍。

我们可以使用动态规划来解决这个问题，设f[i][j]表示前i个接口板能否组成转发能力为j的整机，如果能组成，那么f[i][j]定义为i表示第i个元素为结尾接口板，那么我们有状态转移方程：

f[i][j] = f[i - 1][j] or f[i - 1][j - a[i]]

其中a[i]表示第i个接口板的容量。由于需要记录路径，我们可以使用pre[i][j]来记录f[i][j]的上一个状态。

pre[i][j] = f[i - 1][j - a[i]]

由于每次只需要前一个状态，所以我们可以使用一维的f来进行优化。

最后将符合条件的路径找出，将其分成两部分，分别排序，然后对比输出即可。

题解

为了给两台设备配置接口板，使得每台设备的接口板转发能力之和恰好等于设备的整机转发能力，我们可以利用动态规划来解决这个问题。具体思路如下：

1. 问题分析：

   • 输入中给定的目标设备的转发能力为 ( m )，并且客户订购了 ( n ) 块接口板。根据题目的描述，如果存在解，那么所有接口板的容量之和必定等于 ( 2m )（即两台设备的转发能力总和）。因此，如果这些接口板的总和不等于 ( 2m )，直接输出 -1。

2. 动态规划状态定义：

   • 我们定义 f[i][j] 表示前 ( i ) 个接口板能否组成转发能力为 ( j ) 的整机。如果能组成，那么 f[i][j] 的值为真。我们还需要使用 pre[i][j] 来记录路径，表示 f[i][j] 的上一个状态。

3. 状态转移方程：

   • 状态转移方程为： [ f[i][j] = f[i - 1][j] \text{ or } f[i - 1][j - a[i]] ]
   • 其中，( a[i] ) 表示第 ( i ) 个接口板的容量。

4. 优化：

   • 由于我们只需要使用前一个状态，因此可以将 f 数组优化为一维数组，从而减少空间复杂度。

5. 路径回溯：

   • 一旦找到能够组成转发能力为 ( m ) 的方案，我们需要回溯找到所用的接口板。利用 pre 数组可以帮助我们记录并找出使用了哪些接口板。

6. 结果输出：

   • 将找到的两部分接口板分别排序，然后进行比较，按照题目要求的顺序输出。

代码

Python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    m = int(data[0])  # 读取 m
    n = int(data[1])  # 读取 n
    a = list(map(int, data[2:2 + n]))  # 读取数组 a

    # 如果数组元素的总和不等于 2m，则输出 -1 并退出
    if sum(a) != m * 2:
        print(-1)
        return

    # 初始化前驱数组 pre 和动态规划数组 f
    pre = [[-1] * (m + 1) for _ in range(n)]
    f = [-1] * (m + 1)
    f[0] = 0

    # 动态规划过程
    for i in range(n):
        for j in range(m, a[i] - 1, -1):
            if f[j - a[i]] != -1:
                pre[i][j] = f[j - a[i]]
                f[j] = i

    # 如果能找到一个和为 m 的子集
    if f[m] != -1:
        vis = [False] * n
        i, j = m, f[m]
        while i > 0:
            vis[j] = True
            k = a[j]
            j = pre[j][i]
            i -= k

        ans1, ans2 = [], []
        for i in range(n):
            if vis[i]:
                ans1.append(a[i])
            else:
                ans2.append(a[i])

        # 对两个子集进行排序
        ans1.sort()
        ans2.sort()

        # 比较两个子集，确保 ans1 是字典序较小的
        if ans1[0] > ans2[0] or (ans1[0] == ans2[0] and len(ans1) < len(ans2)):
            ans1, ans2 = ans2, ans1

        # 输出两个子集
        print(" ".join(map(str, ans1)))
        print(" ".join(map(str, ans2)))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();  // 读取输入的数组元素
        }

        // 如果数组元素的总和不等于 2m，则输出 -1 并退出
        if (Arrays.stream(a).sum() != m * 2) {
            System.out.println(-1);
            return;
        }

        // 初始化前驱数组 pre 和动态规划数组 f
        int[][] pre = new int[n][m + 1];
        for (int[] row : pre) Arrays.fill(row, -1);
        int[] f = new int[m + 1];
        Arrays.fill(f, -1);
        f[0] = 0;

        // 动态规划过程
        for (int i = 0; i < n; ++i) {
            for (int j = m; j >= a[i]; --j) {
                if (f[j - a[i]] != -1) {
                    pre[i][j] = f[j - a[i]];
                    f[j] = i;
                }
            }
        }

        // 如果能找到一个和为 m 的子集
        if (f[m] != -1) {
            boolean[] vis = new boolean[n];
            for (int i = m, j = f[m]; i > 0;) {
                vis[j] = true;
                int k = a[j];
                j = pre[j][i];
                i -= k;
            }

            List<Integer> ans1 = new ArrayList<>();
            List<Integer> ans2 = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                if (vis[i]) ans1.add(a[i]);
                else ans2.add(a[i]);
            }

            // 对两个子集进行排序
            Collections.sort(ans1);
            Collections.sort(ans2);

            // 比较两个子集，确保 ans1 是字典序较小的
            if (ans1.get(0) > ans2.get(0) || 
                (ans1.get(0).equals(ans2.get(0)) && ans1.size() < ans2.size())) {
                List<Integer> temp = ans1;
                ans1 = ans2;
                ans2 = temp;
            }

            // 输出两个子集
            for (int i = 0; i < ans1.size(); ++i) 
                System.out.print(ans1.get(i) + (i == ans1.size() - 1 ? "\n" : " "));
            for (int i = 0; i < ans2.size(); ++i) 
                System.out.print(ans2.get(i) + (i == ans2.size() - 1 ? "\n" : " "));
        }
    }
}

C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> m >> n;
    vector<int> a(n);
    for (int i = 0;i < n;++ i) cin >> a[i];
    if (accumulate(a.begin(), a.end(), 0) != m * 2) {
    cout << -1 << endl;
    return 0;
    }
    vector<vector<int>> pre(n, vector<int> (m + 1, -1));
    vector<int> f(m + 1, -1);
    f[0] = 0;
    for (int i = 0;i < n;++ i) {
        for (int j = m;j >= a[i];-- j) if (~f[j - a[i]]) {
            pre[i][j] = f[j - a[i]];
            f[j] = i;
        }
    }
    if (~f[m]) {
        vector<bool> vis(n, false);
        for (int i = m, j = f[m];i > 0;) {
            vis[j] = true;
            int k = a[j];
            j = pre[j][i];
            i -= k;
        }
        vector<int> ans1, ans2;
        for (int i = 0;i < n;++ i) {
            if (vis[i]) ans1.push_back(a[i]);
            else ans2.push_back(a[i]);
        }
        sort(ans1.begin(), ans1.end());
        sort(ans2.begin(), ans2.end());
        if (ans1[0] > ans2[0] || (ans1[0] == ans2[0] && ans1.size() < ans2.size())) swap(ans1, ans2);
        for (int i = 0;i < ans1.size();++ i) cout << ans1[i] << " \n"[i == ans1.size() - 1];
        for (int i = 0;i < ans2.size();++ i) cout << ans2[i] << " \n"[i == ans2.size() - 1];
    }
    return 0;
}