分治限界法装载问题c语言

装载问题是一个经典的分治问题，下面是一个用 C 语言实现的分治限界法装载问题的代码：

#include <stdio.h>
 
#define MAXN 100005
#define MAXW 10005
 
int n, w; // n 个物品，容量为 w 的背包
int wgt[MAXN], val[MAXN]; // wgt: 每个物品的重量；val: 每个物品的价值
 
int max_val; // 装载问题的最大价值
 
void dfs(int i, int cw, int cv) // i: 当前物品编号；cw: 当前背包已经装的重量；cv: 当前背包的总价值
{
    if (cv > max_val) max_val = cv; // 更新最大价值
    if (i > n || cw >= w) return; // 递归结束条件
 
    // 不选第 i 个物品
    dfs(i + 1, cw, cv);
 
    // 选第 i 个物品
    if (cw + wgt[i] <= w) dfs(i + 1, cw + wgt[i], cv + val[i]);
}
 
int main()
{
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &wgt[i], &val[i]);
 
    dfs(1, 0, 0);
    printf("%d\n", max_val);
 
    return 0;
}

这个代码使用了深度优先搜索（DFS）来遍历所有可能的装载方案，并用一个变量 `max_val` 记录最大的装载价值。当搜索到第 i 个物品时，有两种选择：选或不选。如果不选第 i 个物品，则直接递归到下一个物品；如果选第 i 个物品，则将当前背包的总重量和总价值分别加上第 i 个物品的重量和价值，并递归到下一个物品。递归结束的条件是当搜索到第 n 个物品或当前背包已经装满时，直接返回。