回溯法求解01背包问题C语言完整代码

以下是回溯法求解01背包问题的C语言完整代码：

#include <stdio.h>

#define MAXN 1000

int n, c;    // 物品数量、背包容量
int w[MAXN]; // 物品重量
int v[MAXN]; // 物品价值
int cw;     // 当前背包重量
int cp;     // 当前背包中物品总价值
int bestp;  // 当前最优价值
int x[MAXN]; // 背包中物品的状态（0/1）

// 计算当前价值上界
int bound(int i)
{
    int b = cp; // 当前价值
    int cleft = c - cw; // 剩余容量
    
    // 尽量装满剩余容量
    while (i <= n && w[i] <= cleft)
    {
        cleft -= w[i];
        b += v[i];
        i++;
    }
    
    // 还有剩余容量时，用下一个物品的单位价值来装满剩余容量
    if (i <= n)
    {
        b += cleft * v[i] / w[i];
    }
    
    return b;
}

// 回溯搜索
void backtrack(int i)
{
    if (i > n) // 搜索结束
    {
        if (cp > bestp)
        {
            bestp = cp;
        }
        
        return;
    }
    
    // 不装第i个物品
    x[i] = 0;
    backtrack(i + 1);
    
    // 装第i个物品
    if (cw + w[i] <= c) // 可以装下
    {
        x[i] = 1;
        cw += w[i];
        cp += v[i];
        backtrack(i + 1);
        cw -= w[i]; // 回溯
        cp -= v[i]; // 回溯
    }
}

int main()
{
    scanf("%d%d", &n, &c);
    
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &w[i], &v[i]);
    }
    
    bestp = 0;
    cw = cp = 0;
    backtrack(1);
    
    printf("%d\n", bestp);
    
    return 0;
}

请注意，本回答中的代码仅供参考，请勿直接复制使用，否则可能造成不必要的错误。