3-2025年计算机算法分析

必做题 子集和问题(回溯) *

题目描述

已知 $n+1$ 个正数：$w{i}(1\leq i \leq n)$ 和 $M$ ，要求找出${w{i}}$ 的所有子集使得子集中元素之和等于 $M$ 。解采用大小固定的n-元组$(x{1},...,x{n})$ 表达，其中：$x{i}\in{0，1}，1\leq i\leq n$ 。若$x{i}=0$ ，表示解集合不包含 $w{i}$ ；若 $x{i}=1$，表示解集合包含 $w{i}$。隐式约束条件是$\sum{i=1}^nw{i} x{i} =M$。

要求利用回溯方法解决子集和数问题。

输入格式

第一行为一个正整数 $n$ ，表示总集规模；

第二行是正整数 $M$ ，表示子集的和数；

第三行是总集中 $n$ 个正整数，中间用空格隔开。

输出格式

如果有答案，则输出所有满足条件的子集（用固定长度n-元组表示符合条件的一个子集，即每行是一个长度为n的0/1序列），按字典序排列。

如果没有答案，则输出 -1

输入输出样例 #1

输入 #1

4
31
11 13 24 7

输出 #1

0011
1101

输入输出样例 #2

输入 #2

6
30
5 10 12 13 15 18

输出 #2

001001
101100
110010

数据范围

$n\leq 20, \sum w_i,M\leq 10^9$

Bonus

想一想，若只要求判断是否有解，当 $n=40$ 时，有没有在最坏情况下仍能得到答案的算法？

动态规划或者说记忆化搜索，记录不同剩余容量是否有解减少重复计算子问题

• 原题：U407992 子集和数 - 洛谷

解法一：回溯法

• 此题就是简单0/1背包的进阶班，此时要求的是所有组合，尝试利用回溯法进行求解
• 首先是显式回溯，即传入引用
• 注意需要判断有无条件flag

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

vector<int> num;
int flag = true;
void dfs(vector<int>& x, int i, int w)
{
    if (w == 0) {
        flag = false;
        for (const auto& k : x)cout << k;
        cout << endl;
        return;
    }

    if (i==x.size() || w < 0)return;

    dfs(x, i + 1, w);
    x[i] = 1;
    dfs(x, i + 1, w - num[i]);
    x[i] = 0;
    return;
}

int main()
{
    int n, m;
    cin >> n >> m;
    num.resize(n);
    int total = 0;
    for (int i = 0; i < n; i++) { cin >> num[i], total += num[i]; }
    if (total < m) { cout << -1 << endl; return 0; }
    vector<int> x(n,0);
    dfs(x, 0, m);
    if (flag) { cout << -1 << endl; }
    return 0;
}

• 隐式回溯

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

vector<int> num;
int flag = true;
void dfs(vector<int> x, int i, int w)
{
    if (w == 0) {
        flag = false;
        for (const auto& k : x)cout << k;
        cout << endl;
        return;
    }

    if (i==x.size() || w < 0)return;

    dfs(x, i + 1, w);
    x[i] = 1;
    dfs(x, i + 1, w - num[i]);
    return;
}

int main()
{
    int n, m;
    cin >> n >> m;
    num.resize(n);
    int total = 0;
    for (int i = 0; i < n; i++) { cin >> num[i], total += num[i]; }
    if (total < m) { cout << -1 << endl; return 0; }
    vector<int> x(n,0);
    dfs(x, 0, m);
    if (flag) { cout << -1 << endl; }
    return 0;
}

• 优化剪枝条件，记录集合剩余数的和，当依旧所需的和大于剩余的和，无法构成可行解，直接返回

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

vector<int> ans;
int flag;

void dfs(int i, int w, int res, const vector<int>& num) {
    //没有元素处理 || 所需和小于0 || 剩余和小于所需和
    if (i == num.size() || w < 0 || res < w) return;

    // 不选择当前元素
    dfs(i + 1, w, res - num[i], num);

    // 选择当前元素
    ans[i] = 1;
    if (num[i] == w) {
        // 找到一个解，输出路径
        for (const auto& k : ans) cout << k;
        cout << endl;
        flag = true; // 标记找到解
        ans[i] = 0;  // 回溯
        return;
    }
    dfs(i + 1, w - num[i], res - num[i], num);
    ans[i] = 0; // 回溯


}

int main() {
    int n, M;
    cin >> n >> M;
    vector<int> num(n);
    ans.resize(n);
    fill(ans.begin(), ans.end(), 0); // 初始化ans数组
    int total = 0;
    flag = false;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        total += num[i];
    }
    dfs(0, M, total, num);

    if (!flag) {
        cout << -1 << endl;
    }

    return 0;
}

选做题1 圆排列问题

给定n个圆的整数半径序列，将这些圆放到一个矩形框中，每个圆都与矩形框的底边相切，则圆的不同排列会得到不同的排列长度，如下图： 注意：因为圆的半径可能很大，也可能很小，也许会有这种情况出现： 要求找到使得排列长度最小的n个圆的排列。

输入格式:

第一行输入n 值。 第二行输入 n 个圆的整数半径序列。

输出格式:

第一行输出最小的排列长度，精确到小数点后两位，第三位按四舍五入方式处理。 第二行输出该排列对应的圆的编号序列，各半径之间用一个空格分隔。如果有多解，输出字典序最小的序列。

输入样例1:

3
3 3 3

输出样例1:

18.00
1 2 3

输入样例2:

5
1 3 5 7 9

输出样例2:

44.97
1 4 2 5 3

数据范围

n≤9

解法一：回溯法

• 其实答案或者说题目并不准确，没有详细说明多解的答案是取舍后还是原浮点数

• 样例仅仅比较长度四舍五入后两位小数的浮点数，而非完整浮点数，所以必须在比较当前可行解和目前最优解时必须提前四舍五入；

• 在更新逻辑里加入这段代码可以发现样例2错误，

  double tmp = right - left;
  //tmp = round(tmp * 100) / 100.0;
  //判断该排列是否为已计算排列中长度最小的，是则更新最小排列长度
  if (tmp < minlength) {
  
      cout.precision(numeric_limits<double>::digits10 + 1);
      cout << tmp << "," << minlength << endl;
      for (const auto& k : order)cout << k + 1;
      cout << endl;
      minlength = tmp;
      //并更新最小圆排列顺序
      ans_order = order;
  }
  

• 回溯注意剪枝条件，当前圆心横坐标加上当前圆半径如果已经大于目前最优解则跳过

#include<iostream>
#include<vector>
#include<cmath>
#define N 200

using namespace std;

// 半径、圆心横坐标、最短圆排列
double radius[N], centerX[N];
// 最短圆排列长度
double minlength = 0xffffff;
vector<int> order;          // 当前排列的圆的索引
vector<int> ans_order;      // 最短圆排列的索引
// 得到每个圆的圆心位置
double getCenterX(int k, int num) {
    double tmp = 0;
    // 排列最短必定存在一个圆与该圆相切，找到一个与之相切的圆即可得到该圆坐标
    for (int i = 0; i < num; i++) {
        // 相切圆圆心横坐标距求法
        double value = centerX[order[i]] + 2.0 * sqrt(radius[k] * radius[order[i]]);
        if (value > tmp) {
            tmp = value;
        }
    }
    return tmp;
}

// 得到当前圆排列长度
void getLength(int num) {
    double left = 0xffff, right = -0xffff;
    for (int i = 0; i < num; i++) {
        // 众多圆中起始位置最左的就是该排列的左边界
        if (centerX[i] - radius[i] < left) {
            left = centerX[i] - radius[i];
        }
        // 众多圆中末尾位置最右的就是该排列的右边界
        if (centerX[i] + radius[i] > right) {
            right = centerX[i] + radius[i];
        }
    }

    double tmp = right - left;
    // 对长度进行四舍五入到小数点后两位，确保精度一致
    tmp = round(tmp * 100) / 100.0;
    // 判断该排列是否为已计算排列中长度最小的，是则更新最小排列长度
    if (tmp < minlength) {
        minlength = tmp;
        // 并更新最小圆排列顺序
        ans_order = order;
    }
}
vector<bool> vis; // 标记数组，表示某个圆是否已经被使用

// 回溯函数，用于生成所有可能的圆排列
void traceBack(int k, int num) {
    // 全部圆都已参与排列，计算该排列长度
    if (k == num) {
        getLength(num);
    }
    else {
        for (int j = 0; j < num; ++j) {
            if (vis[j]) continue; // 如果当前圆已经被使用，跳过
            double nowX = getCenterX(j, k);
            // 剪枝条件：如果当前圆的右边界加上第一个圆的半径小于已知的最小长度，则继续递归
            if (order.empty() || nowX + radius[j]  < minlength) {
                vis[j] = true;
                centerX[j] = nowX;
                order.push_back(j);
                traceBack(k + 1, num);
                order.pop_back();
                vis[j] = false;
            }
        }
    }
}

int main() {
    int n;
    minlength = 0xffffff;
    cin >> n; // 输入圆的数量
    if (n == 0) {
        return 0; // 如果没有圆，直接退出
    }
    for (int i = 0; i < n; i++) {
        cin >> radius[i]; // 输入每个圆的半径
    }
    vis.resize(n, false); // 初始化标记数组
    traceBack(0, n); // 开始回溯
    printf("%.2f\n", minlength); // 输出最短圆排列的长度
    for (int i = 0; i < n; ++i) {
        // 输出最短圆排列的圆的编号，编号从1开始
        cout << ans_order[i] + 1;
        if (i != n - 1) cout << " ";
    }
    return 0;
}

选做题2 字符序列问题(回溯)

从三个字符的集合[A，B，C]中选取字符，生成一个长度为 N 的字符序列，检验字符序列，检查所有长度为2的子序列，不允许存在两个相同的子序列(不重叠)。例：N = 5时ABCBA是合格的，而序列ABCBC 与ABABC是不合格的，因为其中子序列BC，AB是相同的。 对于由键盘输入的N(1<=N<=12)，求出满足条件的所有字符序列的总数。

例如：N=4 可能的字符序列共计3 3 3 * 3=81个， 去除ABAB, BABA, ACAC, CACA, BCBC, CBCB, AAAA, BBBB, CCCC。 72个符合条件。

输入格式:

字符序列长度N，(1<=N<=12)

输入格式:

满足条件的字符序列总数

输入样例:

4

输出样例:

72

• 题目有错

• 我理解为所以子序列都不可以重复

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_map>
#include <functional>
using namespace std;

int ans = 0;
vector<vector<int>> map(3, vector<int>(3, 0));
void dfs(int n,vector<int>& num)
{
    if (n == 0) {
        ans++;
        for (const auto& k : num)cout << k;
        cout << endl;
        return;
    }
    if(num.empty()){
        for (int i = 0; i < 3; i++)
        {
            num.push_back(i);
            dfs(n - 1, num);
            num.pop_back();
        }
        return;
    }

    int pre = num.back();
    for (int i = 0; i < 3; i++)
        if (map[pre][i]==0) {
            map[pre][i] = 1;
            num.push_back(i);
            dfs(n - 1, num);
            num.pop_back();
            map[pre][i] = 0;
        }
    return;
}
int main()
{
    int n;
    cin >> n;
    vector<int> num;
    dfs(n, num);
    cout << ans;
    return 0;
}

• 原题:U444045 字符序列(characts) - 洛谷

解法一：回溯

• 理解题目后仅仅需要和前一个长度为二的子序列比较

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

int ans = 0;

void dfs(int n, vector<int>& num) {
    if (n == 0) {
        ans++;
        return;
    }
    if (num.size() < 3) {
        for (int i = 0; i < 3; i++) {
            num.push_back(i);
            dfs(n - 1, num);
            num.pop_back();
        }
        return;
    }

    int pre = num.size() - 1;
    for (int i = 0; i < 3; i++) {
        if (num.size() >= 3 && num[pre - 2] == num[pre] && num[pre - 1] == i) continue;
        num.push_back(i);
        dfs(n - 1, num);
        num.pop_back();
    }
    return;
}

int main() {
    int n;
    cin >> n;
    vector<int> num;
    dfs(n, num);
    cout << ans << endl;
    return 0;
}