c# - 如何找到允许的最高变量组合？

Question

我是一名新手程序员，正在寻找解决我的运输问题的最佳算法的建议。

所以我有 12 个变量（随着时间的推移而增加）。我想在那个时刻选择最高允许的变量组合。我有一个允许的唯一组合的 12x12 布尔矩阵。

例如，变量 1 (V1) = 10 秒、V2 = 20 秒、V3 = 12 秒等……但是 V1 不能与 V3 或 V7 组合。V2 不能与 V4、V7 或 V10...等组合使用。

我应该使用什么算法在任何时候选择最高允许的变量组合？

非常感谢您的帮助！

Answer 1

我认为这是一个直截了当的循环-> 最大情况。只需循环每个组合 - 执行您需要的任何操作（v1 + v2） - 如果它高于最大值 - 将其设置为最大值。

最大化关于结构的一些假设：

var combinations = new bool[12,12];
var values = new int[12];

var max = 0;
var maxX = -1;
var maxY = -1;

//Loop across all combinations
for (int x = 0; x < 12; x++)
{
    for (int y = 0; y < 12; y++)
    {
        if(combinations[x,y]) //Check if it's a valid combination
        {
            if(values[x] + values[y] > max)
            {
                max = values[x] + values[y];
                maxX = x;
                maxY = y;
            }
        }
    }
}

编辑：

对于任意子集，这样的事情可能会起作用：

var combinations = new bool[12,12];
var values = new int[12];

var max = 0;

//Get all the other variables this variable can be combined with
for (int i = 0; i < 12; i++)
{
    var validCombinations = new List<int>(){ i };

    for (int k = 0; k < 12; k++)
    {
        if(combinations[i,k])
        {
            validCombinations.Add(k);
        }
    }

    //get the actual values for the variables, and sum them:
    var sum = validCombinations.Select(variable => values[variable]).Sum();

    if(sum > max)
    {
        max = sum;
    }
}