优化这个C#算法

本文关键字：算法优化 | 更新日期: 2023-09-27 17:59:56

这是一个算法问题，我有解决方案，但它有性能问题。

问题描述

有n个变量和m个要求。需求表示为（x<=y），这意味着第x个变量必须小于或等于第y个变量。为每个变量指定小于10的非负数。请计算有多少不同的作业符合所有要求。两个赋值是不同的，当且仅当在这两个赋值中至少有一个变量被赋予不同的编号。在1007之前将答案模块化。

输入格式：

输入的第一行包含两个整数n和m。然后跟随m行，每行包含2个空格分隔的整数x和y，这意味着一个要求（x<=y）。

输出格式：

在一行中输出答案。

限制：

0<n<14

0<m<200

0<=x、 y<n

样本输入：

6 7

1 3

0 1

2 4

0 4

2 5

3 4

0 2

样本输出：

1000

以下是我的解决方案。当n＝13和m＝199时，得到结果需要很长时间，但可接受的时间是5秒。

那么，有人能想出更好的方法来进一步优化吗？非常感谢。

我目前的解决方案：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication81
{
    class Program
    {
        const int N = 10;
        static List<Condition> condition = new List<Condition>();
        static void Main(string[] args)
        {
            string[] line1 = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            int n = int.Parse(line1[0]);
            int m = int.Parse(line1[1]);
            for (int i = 0; i < m; i++)
            {
                string[] line = Console.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
                condition.Add(new Condition()
                {
                    X = int.Parse(line[0]),
                    Y = int.Parse(line[1])
                });
            }
            //
            List<int[]> rlist = new List<int[]>();
            for (int j = 0; j < N; j++)
            {
                int[] assignments = new int[n];
                for (int i = 0; i < n; i++)
                    assignments[i] = -1;
                assignments[0] = j;
                rlist.Add(assignments);
            }
            for (int j = 1; j < n; j++)
            {
                List<int[]> rlist2 = new List<int[]>(rlist.Count*5);
                for (int k = 0; k < rlist.Count; k++)
                {
                    for (int l = 0; l < N; l++)
                    {
                        rlist[k][j] = l;
                        if (CanPassCondition(rlist[k]))
                            rlist2.Add((int[])rlist[k].Clone());
                    }
                }
                rlist = rlist2;
            }
            Console.Write(rlist.Count % 1007);
        }

        private static bool CanPassCondition(int[] p)
        {
            foreach (var c in condition)
            {
                if (p[c.X] == -1 || p[c.Y] == -1)
                    continue;
                if (p[c.X] > p[c.Y])
                    return false;
            }
            return true;
        }
    }
    class Condition
    {
        public int X;
        public int Y;
        public override string ToString()
        {
            return string.Format("x:{0}, y:{1}", X, Y);
        }
    }
}

优化这个C#算法

这里有一个Java解决方案，即使n=13，m=199:，它也能很快地工作

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Assignments
{
    private static Map <String, Long> solutions = new HashMap <String, Long> ();
    private static boolean [][] constraints;
    private static long solve (int n, int [] low, int [] high)
    {
        StringBuilder sb = new StringBuilder ();
        for (int i = 0; i < n; i++)
        {
            sb.append (low [i]);
            sb.append (high [i]);
        }
        String signature = sb.toString ();
        Long result = solutions.get (signature);
        if (result == null)
        {
            result = Long.valueOf (doSolve (n, low, high));
            solutions.put (signature, result);
        }
        return result.longValue ();
    }
    private static long doSolve (int n, int [] low, int [] high)
    {
        if (n == 0) return 1;
        else
        {
            long result = 0;
            for (int i = low [n - 1]; i <= high [n - 1]; i++)
            {
                int [] l = new int [n - 1];
                int [] h = new int [n - 1];
                for (int j = 0; j < n - 1; j++)
                {
                    l [j] = constraints [n - 1][j] ? Math.max (low [j], i) : low [j];
                    h [j] = constraints [j][n - 1] ? Math.min (high [j], i) : high [j];
                }
                result += solve (n - 1, l, h);
            }
            return result;
        }
    }
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = 
            new BufferedReader (
                new InputStreamReader(System.in));
        String nm = reader.readLine ();
        String [] pair = nm.split(" ");
        int n = Integer.parseInt(pair [0]);
        int m = Integer.parseInt(pair [1]);
        constraints = new boolean [n][];
        for (int i = 0; i < n; i++)
            constraints [i] = new boolean [n];
        int [] low = new int [n];
        int [] high = new int [n];
        for (int i = 0; i < n; i++)
            high [i] = 9;
        for (int i = 0; i < m; i++)
        {
            String ab = reader.readLine();
            pair = ab.split (" ");
            int a = Integer.parseInt(pair [0]);
            int b = Integer.parseInt(pair [1]);
            constraints [a][b] = true;
        }
        System.out.println(solve (n, low, high));
    }
}

事实上，一旦你有13个变量，你可能只有156（13*12）个有意义的约束，但是。

样本输入：

13 1
3 8

输出：

5500000000000

另一个样本输入：

输出：