回溯算法

#include <stdio.h>
#include <string.h>   
#define MAXN 20
//全局变量 
int w[]={0,5,2,6,4,3} ;
int n=5,W=10; //船的容量和载重
int maxw=0;   //存放最优解的总重量,初值是0
int x[MAXN];  //存放最优解向量,初值是0
int minnum=999999;   //存放最优解的集装箱个数，初值为最大值

/**
num :选择的集装箱个数;
tw :  已经装载到第一艘轮船上的集装箱重量之和
rw :  剩余集装箱的重量和
op : 表示一个解,即一个选择方案，选择时，op=1,不选时，op=0
i : 表示考虑的第i个集装箱
*/
void dfs(int num,int tw,int rw,int op[],int i){
	if(i>n){  //i>n说明所有的集装箱都判断完了 
		if(tw==W&&num<minnum){ //满足这个条件即为最优解，则覆盖之前的解 
			maxw=tw;
			minnum=num;
			for(int j=1;j<=n;j++){
				x[j]=op[j];  //把最优解的值依次赋给最优解向量 
			}
		}
	}else{  //没到最后一个集装箱则需要判断当前这个集装箱是选还是不选 
		op[i]=1;  //如果选择 
		if(tw+w[i]<=W){  //判断剪枝条件 
			dfs(num+1,tw+w[i],rw-w[i],op,i+1);
		}
		op[i]=0;  //如果不选
		if(tw+rw-w[i]>=W){  //判断剪枝条件 
			dfs(num,tw,rw-w[i],op,i+1);
		} 
	}
}
	
void displaySolution(int n){
	for(int i=1;i<=n;i++){
		if(x[i]==1){
			printf("选择第%d个集装箱\n",i);
		}
	}
	printf("总重量为%d\n",maxw);
}
	
int main(){
	int op[MAXN];   //op存放所有可行解 
	int rw;
	memset(op,0,sizeof(op));  //初始化为0 
	for(int i=1;i<=n;i++){
		rw=rw+w[i];   //初始剩余量=所有集装箱饿和 
	}
	dfs(0,0,rw,op,1);  //从第一个开始
	displaySolution(n);  //输出解
	return 0; 
} 

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

// Golang 代码实现
var res [][]int
 
func permute(nums []int) [][]int {
    res = [][]int{}
    backtrack(nums, 0)
    return res
}
 
func backtrack(nums []int, idx int) {
    if idx == len(nums) {
        temp := make([]int, len(nums))
        copy(temp, nums)
        res = append(res, temp)
        return
    }
    for i := idx; i < len(nums); i++ {
        nums[i], nums[idx] = nums[idx], nums[i]
        backtrack(nums, idx+1)
        nums[i], nums[idx] = nums[idx], nums[i]
    }
}

// C 语言代码实现
#include<stdio.h>
void perm(char s[],int k,int n){
    int i;
    char tmp;
    if(k==n-1){
        for(i=0;i<n;i++)
            printf("%c",s[i]);
        printf("\n");
    }else{
        for(i=k;i<n;i++){
            if (i!=k)
                tmp = s[k];s[k] = s[i];s[i] = tmp;//交换s[k]与s[i] 
            perm(s,k+1,n);
            if (i!=k)
                tmp = s[k];s[k] = s[i];s[i] = tmp;//交换s[k]与s[i],恢复环境即回溯。 
        }
    }
}
int main(){
    int n=3;
    char s[] = "123";
    perm(s,0,n);
}