算法（三）回溯法

https://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_label3_1

（8）健康的荷斯坦奶牛？

字典序最小：注意这里从1往0开始枚举，因为题目希望字典序最小

import java.util.Scanner;
public class Main {static int v;static int[] need;static int g;static int[][] have;static int[] select;static int min = Integer.MAX_VALUE;static int[] best;static int flag = 0;public static void main(String[] args) {	Scanner in = new Scanner(System.in);v = in.nextInt();need = new int[v + 1];for(int i = 1;i <= v;i++) {need[i] = in.nextInt();}g = in.nextInt();select = new int[g + 1];best = new int[g + 1];for(int i = 1;i <= g;i++) {select[i] = 0;best[i] = 0;}have = new int[g + 1][v + 1]; for(int i = 1;i <= g;i++) {for(int j = 1;j <= v;j++) {have[i][j] = in.nextInt();}}dfs(1,0);System.out.print(min + " ");for(int i = 1;i <= g;i++) {if(best[i] == 1) {System.out.print(i);}if(i < g && best[i] == 1) {System.out.print(" ");}}}public static void dfs(int t,int num) {if(num >= min) return;if(t > g) {if(judge(select)) {if(num < min) {min = num;for(int i = 1;i <= g;i++) {best[i] = select[i];}}}}else {//1、多种情况，注意这里从1往0开始枚举（因为题目希望字典序最小，故前面的要先考虑先选）for(int i = 1;i >= 0;i--) {//2、处理select[t] = i;//3、判断if(i == 0) {dfs(t + 1,num);}else if(i == 1) {dfs(t + 1,num + 1);}//4、回复select[t] = 0;}}}public static boolean judge(int[] select) {for(int j = 1;j <= v;j++) {int t = 0;for(int i = 1;i <= g;i++) {if(select[i] == 1) {t += have[i][j];}}if(t < need[j]) {return false;}}return true;}}

（9）变换？？？？

https://www.luogu.com.cn/problem/P1037

import java.util.Scanner;
public class Main {static int[][] rule = new int[10][10];static int result = 0;static int num;public static void main(String[] args) {	Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();for(int a = 0;a < k;a++) {int i = in.nextInt();int j = in.nextInt();rule[i][j] = 1;}num = get(n);}public static void dfs(int t) {if(t > num) {}else {}}public static boolean judge(int[] select) {for(int j = 1;j <= v;j++) {int t = 0;for(int i = 1;i <= g;i++) {if(select[i] == 1) {t += have[i][j];}}if(t < need[j]) {return false;}}return true;}public static int get(int n) {int o = 0;while(n != 0) {num++;n /= 10;}return o;}}

（10）盾神与砝码称重？？

思路：

（1）每个砝码都可以选择放砝码盘、物品盘、不放（易错！）

（2）类似于0-1背包问题

https://www.dotcpp.com/oj/problem1548.html

回溯

import java.util.*;public class Main
{static int m = 0,n = 0;static int[] fa = new int[25];static boolean flag = false;static int w;static int sum = 0;public static void main(String args[]) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();for(int i = 1;i <= n;i++) {fa[i] = in.nextInt();}for(int i = 0;i < m;i++) {w = in.nextInt();flag = false;dfs(1);if(flag) {System.out.println("YES");}else {System.out.println("NO");}}}public static void dfs(int t) {if(t > n) {if(sum == w) {flag = true;}}else {for(int i = 0;i < 3;i++) {if(i == 0) {dfs(t + 1);}if(i == 1) {sum += fa[t];dfs(t + 1);sum -= fa[t];}if(i == 2) {sum -= fa[t];dfs(t + 1);sum += fa[t];}}}}}

非回溯

import java.util.*;public class Main
{static int m = 0,n = 0;static int[] fa = new int[25];static boolean flag = false;static int w;public static void main(String args[]) {Scanner in = new Scanner(System.in);n = in.nextInt();m = in.nextInt();for(int i = 1;i <= n;i++) {fa[i] = in.nextInt();}for(int i = 0;i < m;i++) {w = in.nextInt();flag = false;dfs(0,1);if(flag) {System.out.println("YES");}else {System.out.println("NO");}}}public static void dfs(int now,int index) {if(now == w) {flag = true;return ;}if(index > n) {return ;}dfs(now + fa[index],index + 1);dfs(now - fa[index],index + 1);dfs(now,index + 1);}}

三、排序树问题

1、概念

当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。例如旅行售货员问题(如下图)的解空间树是一棵排列树，这类排列树通常有n!个叶结点。遍历子集树的算法需Ω(n!)计算时间。

根为第一层，n个数，n+1 层，从第一到第n个进行

特别适用于排序 序列中

2、解题思路

for if swap 处理 递归 恢复

/*** * output(x)     树一次遍历结束，记录或输出得到的可行解x* constraint(t) 当前结点的题目约束函数* bount(t)      当前结点的数据限界函数* @param t      t为当前解空间的层数* @param n      n为条件给的个数*/void backtrack(int t){if(t > n){//进行当前求最值、是否符合题意等情况的判断，符合则记录或输出！！！output(x);}else{//第t层有（n-t+1）种交换方式for (int i = t; i <= n; i++) {//1、（判断准备工作）先判断再交换（最后计算）//判断（最优性剪枝和可行性剪枝、是否已访问等）if(constraint(t) && bount(t)){//交换swap(x[t], x[i]);//（最后计算）...backtrack(t+1);swap(x[t], x[i]);}//2、（判断准备工作）先交换再判断（最后计算）//swap(x[t], x[i]);  //if (constraint(t)&&bound(t)) backtrack(t+1);  //swap(x[t], x[i]); }}}backtrack（1）	//第一层开始从头到尾
backtrack（2）	//第一层固定（起点固定），从第二层开始

java swap()函数

	public static void swap(int i,int j) {int t = x[i];x[i] = x[j];x[j] = t;}

3、技巧

（1）注意初始化

初始化序列干脆为1 2 3 4 …… n

（2）求最优记录输出要判断

（3）推荐使用顺序：判断-交换-计算

（4）为什么要swap呢

这个swap其实是“挪”向了同层的其他节点，但这个地方我们没有建树，直接通过在这条路径上进行swap得到。

譬如，一条12345路径，我们从1出发1->2->3->4->5

那我们backtrace（2）的时候会把2和345交换位置，就是为了获得1->3,1->4,1->5开头的路径。

（5）一般数组下标都是从1开始，便于根据题意操作

（6）由backpack(t+1)知：若当前为第t层，则上一节点在第(t-1)层为x[t-1]，下一节点为x[i]

4、例题

（1）全排列问题

https://blog.csdn.net/long_long_int/article/details/79930888

非字典序 ：swap

#include
using namespace std;
int n,a[100];
void dfs(int t)
{if(t>n){for(int i=1;i<=n;i++){cout<>n){for(int i=1;i<=n;i++){a[i]=i;//初始化a数组，第一次干脆定从小到大}dfs(1);}
}

字典序：子集树

#include
using namespace std;
int n,a[100],v[100];
//a数组用于保存每一次的排列，v数组用于判断数字是不是已经被选过 
void dfs(int dp)//dp从1到n，执行n次，每次选择一个数 
{if(dp>n)//dp为n+1的时候，就说明已经选了n个，可以输出了； {for(int i=1;i<=n;i++){cout<>n){dfs(1);}
}

（2）旅行商问题

起点已定，故从第2层开始即可

https://blog.csdn.net/lfb637/article/details/80635047

/**@回溯-旅行商(TSP)问题
*/
#include
#include
#define MAX 100
using  namespace std;
int n;                               //城市个数
int a[MAX][MAX];                   //城市间距离
int x[MAX];                       //记录路径
int bestx[MAX]  = {0};           //记录最优路径
int bestp = 63355;              //最短路径长
int cp = 0;                    //当前路径长
void backpack(int t){if(t>n){//要能回去且距离仍最小if((a[x[n]][1])&&(a[x[n]][1]+cp>n;      //顶点数//初始化序列for(int i = 1;i<=n;i++){x[i] = i;}cout<<"输入城市之间的距离(0表示城市间不通):"<>a[i][j];}}//起点已定，故从第2层开始即可backpack(2);cout<<"最少旅行费用为: "<

import java.util.Scanner;
public class Main {static int n;static int[][] a;static int[] x;static int now;static int[] r;static int min = Integer.MAX_VALUE;public static void main(String[] args) {	Scanner in = new Scanner(System.in);n = in.nextInt();a = new int[n + 1][n + 1];r = new int[n + 1];x = new int[n + 1];for(int i = 1;i <= n;i++) {x[i] = i;}for(int i = 1;i <= n;i++) {for(int j = 1;j <= n;j++) {a[i][j] = in.nextInt();}}dfs(2);System.out.println(min);for(int i = 1;i <= n;i++) {System.out.print(r[i]);}System.out.print(r[1]);}public static void dfs(int t) {if(t > n) {if(a[x[n]][x[1]] != 0 && now + a[x[n]][x[1]] < min) {min = now + a[x[n]][x[1]];for(int i = 1;i <= n;i++) {r[i] = x[i];}}}else {for(int i = t;i <= n;i++) {if(a[x[t - 1]][x[i]] != 0 && now + a[x[t - 1]][x[i]] < min) {now += a[x[t - 1]][x[i]];swap(i,t);dfs(t + 1);swap(i,t);now -= a[x[t - 1]][x[i]];}}}}public static void swap(int i,int j) {int t = x[i];x[i] = x[j];x[j] = t;}}

#include
using namespace std;
#define MAX 200
int* x1;//作业Ji在机器1上的工作时间
int* x2;//作业Ji在机器2上的工作时间
int number=0;//作业的数目
int* xorder;//作业顺序
int* bestorder;//最优的作业顺序
int bestvalue=MAX;//最优的时间
int xvalue=0;//当前完成用的时间
int f1=0;//机器1完成的时间
int* f2;//机器2完成的时间void backtrack(int t)
{if(t>number){if(xvalue < bestvalue){for(int i=1;i<=number;i++) bestorder[i]=xorder[i];bestvalue=xvalue;}}else{for(int i=t;i<=number;i++){//1、判断f1+=x1[xorder[i]];//计算该作业总时间f2[t]=(f2[t-1]>f1?f2[t-1]:f1)+x2[xorder[i]];//算入总时间xvalue+=f2[t];if(xvalue>number;x1=new int[number+1];x2=new int[number+1];xorder=new int[number+1];bestorder=new int[number+1];f2=new int[number+1];x1[0]=0;x2[0]=0;xorder[0]=0;bestorder[0]=0;f2[0]=0;cout<<"请输入每个作业在机器1上所用的时间："<>x1[i];}cout<<"请输入每个作业在机器2上所用的时间："<>x2[i];}for(i=1;i<=number;i++) xorder[i]=i;backtrack(1);cout<<"最节省的时间为："<

#include
#include
using namespace std;
#define MAX 200float minlen=10000,x[4],r[4];//当前最优值,当前圆排列圆心横坐标,当前圆排列
int n;//圆排列中圆的个数
//计算当前所选择圆的圆心横坐标
float center(int t)
{float temp=0;for(int j=1;jtemp) temp=valuex;}return temp;
}
//计算当前圆排列的长度
void compute()
{float low=0,high=0;for(int i=1;i<=n;i++){if(x[i]-r[i]high) high=x[i]+r[i];}if(high-lown) compute();else{for(int j=t;j<=n;j++){//为什么这样不可以？？把计算放在前面了！//float centerx=center(t);//if(centerx+r[t]+r[1]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！