分支界定法解整数规划c代码

下面是使用分支界定法解整数规划的一个简单的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100 // 变量个数
#define M 100 // 约束个数

int n, m; // 变量个数和约束个数
double c[N]; // 目标函数系数
double a[M][N]; // 约束系数
double b[M]; // 右端常数
int x[N]; // 解向量
double best; // 当前最优解

void solve(int k, double z, double lb, double ub)
{
    if (k == n) // 找到一个可行解
    {
        if (z > best) // 更新最优解
        {
            best = z;
            memcpy(x, a[n], sizeof(x));
        }
        return;
    }
    int j = -1;
    double max = -1;
    for (int i = 0; i < n; i++) // 选择下一个分支变量
    {
        if (!a[n][i] && c[i] > max)
        {
            max = c[i];
            j = i;
        }
    }
    if (j < 0) // 所有整数变量都取整了
    {
        if (z > best) // 更新最优解
        {
            best = z;
            memcpy(x, a[n], sizeof(x));
        }
        return;
    }
    // 分支
    double y[N];
    memcpy(y, a[n], sizeof(y));
    a[n][j] = ub;
    solve(k + 1, z + ub * c[j], lb, ub);
    memcpy(a[n], y, sizeof(y));
    a[n][j] = lb;
    solve(k + 1, z + lb * c[j], lb, ub);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &c[i]);
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%lf", &a[i][j]);
        }
        scanf("%lf", &b[i]);
    }
    for (int i = 0; i < n; i++)
    {
        a[m][i] = 1;
    }
    solve(0, 0, 0, 1e9);
    printf("%.2lf\n", best);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", (int)(x[i] + 0.5));
    }
    printf("\n");
    return 0;
}

该代码采用了递归的方式实现分支界定法，具体而言，`solve`函数表示求解当前子问题的过程。其中，`k`表示当前处理的变量个数，`z`表示当前目标函数值，`lb`和`ub`分别表示分支变量的下界和上界。在函数中，首先检查是否已经找到了可行解，如果是，则更新最优解，并返回；否则，选择下一个分支变量，进行分支，递归调用`solve`函数。最后，程序输出最优解和对应的解向量。

需要注意的是，为了方便处理，代码中使用了一个长度为`n+1`的一维数组`a`，其中前`m`行存储约束系数，第`n`行存储解向量，最后一行存储一个全1的向量，用于表示`x`的取值范围。