订单分配

#include<bits/stdc++.h>
using namespace std;
vector<int>res;
vector<bool>tag;
double rmax=0;
void solve(vector<vector<double>>&A,vector<int>&v,double maxnum,int j){
    if(j>=A[0].size()){
        if(rmax<maxnum){
            rmax=maxnum;
            res=v;
        }
        return;
    }
    for(int i=0;i<A[0].size();i++){
        if(!tag[i]){
            tag[i]=true;
            v.push_back(i);
            solve(A,v,maxnum+A[j][i],j+1);
            v.pop_back();
            tag[i]=false;
        }
    }
}
int main(){
    int n;
    double a;
    cin>>n;
    vector<vector<double> >A;
    for(int i=0;i<n;i++){
        vector<double>temp;
        for(int j=0;j<n;j++){
            cin>>a;
            temp.push_back(a);
        }
        A.push_back(temp);
    }
    vector<int>v;
    tag=vector<bool>(n,false);
    solve(A,v,0,0);
    cout<<fixed<<setprecision(2)<<rmax<<endl;
    for(int i=0;i<n;i++)cout<<i+1<<" "<<res[i]+1<<endl;
    return 0;
}

import java.util.*;
//过100%
public class Main {
    private double t = 0.00;
    private int[] flag;
    private double res = -1000.00;//0.00只能过80%
    private ArrayList<Integer> add;
    public void Solution(double[][] nums)
    {
        int n = nums.length;
        flag = new int[n];
        for(int i = 0;i<n;i++)
        {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(i+1);
            flag[i] = 1;
            t = nums[0][i];
            Best(temp, nums, 1);
            t = 0.00;
            flag[i] = 0;
        }
        System.out.println(String.format("%.2f", res));
        for(int i = 0;i<add.size();i++)
        {
            System.out.println(i+1 +" "+ add.get(i));
        }
    }
    public void Best(ArrayList<Integer> temp, double[][] nums, int end)
    {
        if(end==nums.length)
        {
            if(res<t)
            {
                res = t;
                add = (ArrayList<Integer>) temp.clone();
            }
        }
        for(int i = 0;i<nums.length;i++)
        {
            if(flag[i]!=1)
            {
                flag[i] = 1;
                t += nums[end][i];
                temp.add(i+1);
                Best(temp, nums, end+1);
                temp.remove(temp.size()-1);
                t -= nums[end][i];
                flag[i] = 0;
            }
        }
    }
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        while(in.hasNext())
        {
            int n = in.nextInt();
            double[][] nums = new double[n][n];
            for(int i = 0;i<n;i++)
                for(int j = 0;j<n;j++)
                    nums[i][j] = in.nextDouble();
            Main s = new Main();
            s.Solution(nums);
        }
    }
}

//每行每列选一个，且不重复，类似于N皇后问题与全排列问题，回溯法解决
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

void recur(vector<vector<double>>& nums, vector<int>& ans, vector<int>& curT, vector<bool>& visited, double curProfit, double& sum, int row){
    int n = nums.size();
    //退出条件
    if(row == n){
        if(curProfit > sum){        //更新最大和与每行对应的列
            sum = curProfit;
            ans = curT;
        }
        return;
    }
    //轮流考虑当前row行，选取每一列的可能性
    for(int i=0; i<n; i++){
        //该列未选取
        if(!visited[i]){
            //更新状态
            visited[i] = true;
            curProfit += nums[row][i];
            curT[row] = i;
            
            recur(nums, ans, curT, visited, curProfit, sum, row+1);
            //还原状态
            visited[i] = false;
            curProfit -= nums[row][i];
        }
    }
}

int main(){
    int n;
    while(cin >> n){
        vector<vector<double>> nums(n, vector<double>(n));
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++)
                cin >> nums[i][j];
        }
        //最大和的情况下，各行选取的列； 当前状态下各行选取的列
        vector<int> ans(n), curT(n);
        //记录已选取的列，避免重复
        vector<bool> visited(n, false);
        //最大和与当前和
        double sum = -1, curProfit = 0;
        //初始行号
        int row = 0;
        recur(nums, ans, curT, visited, curProfit, sum, 0);
        
        printf("%4.2f\n", sum);
        
        for(int i=0; i<n; i++){
            cout << i+1 << ' ' << ans[i]+1 << endl;
        }
    }
    return 0;
}

import java.io.*;
/**
 * @Description: 计算并保存所有分组方式下的 score 值，取最大值 优化方向 -> 循环计算并 始终存储一组最好的值
 * @Param:
 * @return:
 * @Author: xulifeng
 * @Date: 3/10/2022
 */
public class Main {
    // 原始分配表
    static double[][] score;
    // 最终分配结果
    static double[][] bestPath;
    // 当前分配方式
    static double[][] curPath;
    // 最大score
    static double maxScore = 0;
    // 订单数
    static int orderNum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        orderNum = Integer.parseInt(br.readLine());
        score = new double[orderNum][orderNum];
        bestPath = new double[orderNum][orderNum];
        curPath = new double[orderNum][orderNum];
        // 填充score、bestPath、curPath
        for (int i = 0; i < orderNum; i++) {
            String[] oneRowScore = br.readLine().split(" ");
            for (int j = 0; j < orderNum; j++) {
                score[i][j] = Double.parseDouble(oneRowScore[j]);
                bestPath[i][j] = 0;
                curPath[i][j] = 0;
            }
        }
        //从第0行开始递归
        backTracing(0, orderNum);
        System.out.printf("%.2f",maxScore);
        System.out.println();

        for (int i = 0; i < orderNum; i++) {
            for (int j = 0; j < orderNum; j++) {
                if (bestPath[i][j] != 0) {
                    // +1是因为订单 车是从1开始 而数组从零开始
                    System.out.print(i+1);
                    System.out.print(" ");
                    System.out.println(j+1);
                }
            }
        }
    }
    /**
     * @Description: 回溯算法 检查这个位置是否还能存放
     * @Param: 当前行curRow 总列数
     * @return:
     * @Author: xulifeng
     * @Date: 3/9/2022
     */
    public static void backTracing(int curRow, int totalCol) {
        // 遍历完所有行时 row 和 col 大小一样
        if (curRow == orderNum) {
            // 将深拷贝的数据添加进result 浅拷贝会因为回溯全部变为0
            double curScore = computeCurScore();
            if (curScore > maxScore) {
                maxScore = curScore;
                bestPath = deepCopy();
            }
            return;
        }
        //index 其实也为行 从上往下判断
        for (int index = 0; index < totalCol; index++) {
            if (isValid(curRow, index)) {
                // 可以分配订单
                curPath[curRow][index] = score[curRow][index];
                backTracing(curRow+1,totalCol);
                //撤销当前的操作 因为撤销操作 所有的bestPath数组最终都变成了0回溯不可避免的事情
                curPath[curRow][index] = 0;
            }
        }
    }
    // 检查目前是否能在 row col这个位置存放数据 要求同一列只能有一个数据
    public static boolean isValid(int curRow, int curCol){
        //检查[curRow][curCol]这一列之前是否已经有数据
        for (int i = 0; i < curRow; i++) {
            if (curPath[i][curCol] != 0) {
                return false;
            }
        }
        return true;
    }
    // 计算当前分配方式下的score
    public static double computeCurScore() {
        double score = 0;
        for (int i = 0; i < orderNum; i++) {
            for (int j = 0; j < orderNum; j++) {
                score += curPath[i][j];
            }
        }
        return score;
    }
    // 深拷贝
    public static double[][] deepCopy() {
        double[][] temp = new double[orderNum][orderNum];
        for (int i = 0; i < orderNum; i++) {
            for (int j = 0; j < orderNum; j++) {
                temp[i][j] = curPath[i][j];
            }
        }
        return temp;
    }
}

public class Main {

    public static List<Integer> best = new ArrayList<>();

    public static void main(String[] args) {
        double[][] matrix = {{1.08, 1.25, 1.5},
                {1.5, 1.35, 1.75},
                {1.22, 1.48, 2.5}};

        double grade = allPl(matrix, 0, new ArrayList<>(), 0);
        System.out.println(grade);
        best.stream().forEach(item -> System.out.println(item + 1));
    }

    public static double allPl(double[][] matrix, double maxNum, List<Integer> res, double num) {
        if (res.size() == matrix.length && num > maxNum) {
            maxNum = num;
            best = new ArrayList<>(res);
            return maxNum;
        }
        for (int i = 0; i < matrix.length; i++) {
            if (res.contains(i)) {
                continue;
            }
            res.add(i);
            num += matrix[res.size() - 1][i];
            maxNum = allPl(matrix, maxNum, res, num);
            res.remove(res.size() - 1);
            num -= matrix[res.size()][i];
        }
        return maxNum;
    }
}

import java.util.*;
public class Main {

    static boolean[] visited;
    static double max = -1000;
    static int n;
    static double[][] nums;
    static List<int[]> relation = new ArrayList<>();
    static List<int[]> maxRelation = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        nums = new double[n][n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                nums[i][j] = in.nextDouble();
            }
        }
        helper(0, 0);
        System.out.println(String.format("%.2f", max));
        for (int[] re: maxRelation) {
            System.out.println((re[0] + 1) + " " + (re[1] + 1));
        }
    }

    private static void helper(int row, double count) {
        // 这个时候计算最大值
        if (row == n) {
            if (count >= max) {
                if (count == 0) {
                    max = count;
                    List<int[]> list = new ArrayList<>();
                    for (int i = 0; i < n; i++) {
                        int[] temp = new int[2];
                        temp[0] = i;
                        temp[1] = i;
                        list.add(temp);
                    }
                    maxRelation = new ArrayList<>(list);
                } else {
                    max = count;
                    maxRelation.clear();
                    maxRelation = new ArrayList<>(relation);
                }
            }
            // 这个时候记录订单
            return;
        }
        for (int i = 0; i < n ; i++) {
            if (!visited[i]) {
                // 同时记录订单与司机的关系
                int[] relationArr = new int[2];
                relationArr[0] = row;
                relationArr[1] = i;
                relation.add(relationArr);
                visited[i] = true;
                helper(row + 1, count + nums[row][i]);
                relation.remove(relation.size() - 1);
                visited[i] = false;
            }
        }
    }

}

def assign_order(A: list):
    n = len(A)
    result = []
    m = [-float('inf')]
    visited = [[0] * n] * n
    def dfs(cur, n, t, res):
        if cur > n:
            sumt = sum(t)
            if sumt > m[0]:
                m[0] = sumt
                result.append(res)
            return 
        
        for i in range(n + 1):
            if not visited[cur][i]:
                visited[cur][i] = 1
                dfs(cur + 1, n, t + [A[cur][i]], res + [i + 1])
                visited[cur][i] = 0
                
    dfs(0, n - 1, [], [])
    print('{:.2f}'.format(m[0]))
    for i in range(n):
        print('{} {}'.format(i + 1, result[-1][i]))

n = int(input().strip())
matrix = []
for i in range(n):
    matrix.append(list(map(float, input().strip().split())))

assign_order(matrix)