整数规划—分枝定界法C语言

整数规划是一种优化问题，它要求在一组整数的可行解集合中找到一个最优解。分枝定界法是一种求解整数规划问题的有效方法。以下是一个使用C语言实现分枝定界法的示例代码。

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

#define MAXN 1000
#define MAXM 1000

int n, m;
int c[MAXN], a[MAXM][MAXN], b[MAXM];
int x[MAXN], bestx[MAXN];
int bestc, curc;

void dfs(int i)
{
    if (i > n) {
        if (curc > bestc) {
            bestc = curc;
            for (int j = 1; j <= n; j++) {
                bestx[j] = x[j];
            }
        }
        return;
    }

    if (curc + c[i] <= bestc) {
        return;
    }

    x[i] = 1;
    int sum = 0;
    for (int j = 1; j <= m; j++) {
        int ok = 1;
        for (int k = 1; k <= n; k++) {
            if (a[j][k] && x[k] == 0) {
                ok = 0;
                break;
            }
        }
        if (ok) {
            sum += b[j];
        }
    }
    curc += sum;
    dfs(i + 1);
    curc -= sum;

    x[i] = 0;
    dfs(i + 1);
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
        scanf("%d", &b[i]);
    }

    dfs(1);

    printf("bestc = %d\n", bestc);
    for (int i = 1; i <= n; i++) {
        printf("%d ", bestx[i]);
    }
    printf("\n");

    return 0;
}

该代码实现了一个简单的整数规划求解器，用于解决如下形式的整数规划问题：

$$\max \sum_{i=1}^n c_i x_i$$

$$\text{s.t.} \sum_{i=1}^n a_{ji} x_i \leq b_j, j = 1, 2, \cdots, m$$

$$x_i \in \{0, 1\}, i = 1, 2, \cdots, n$$

其中，$n$表示变量个数，$m$表示约束个数，$c_i$表示第$i$个变量的系数，$a_{ji}$表示第$j$个约束中第$i$个变量的系数，$b_j$表示第$j$个约束的右端常数。