用c语言写有n个重量分别为w1，w2,...,wn的物品，他们的价值分别为v1，v2，...,vn，给定一个容量为W的背包。请使用回溯算法（代码应包含左剪枝+右剪枝）求出寻取一部分物品放入背包中，恰好放满背包时，背包中物品的最大价值。 【输入形式】 输入包含4行 第一行为n ，表示物品数量 第二行为物品价值，包含n个整数，以空格作为间隔 第三行为物品重量，包含n个整数，以空格作为间隔 第四行为背包容量W 【输出形式】 输出为一个整数，即满足条件时，背包中物品的最大价值。 【样例输入】 5 0 5 3 2 1 0 4 4 3 1 6 【样例输出】 8

以下是回溯算法的 C 语言代码，包含左剪枝和右剪枝：

#include <stdio.h>

#define MAX_N 100

int n, W;
int w[MAX_N], v[MAX_N];
int max_value = 0, cur_value = 0, cur_weight = 0;

void backtrack(int i) {
    // 右剪枝：超过背包容量或者已经搜索完所有物品
    if (cur_weight > W || i == n) {
        return;
    }
    // 左剪枝：当前价值 + 剩余物品的最大价值 <= 当前最大价值
    int remaining_value = 0;
    for (int j = i; j < n; j++) {
        remaining_value += v[j];
    }
    if (cur_value + remaining_value <= max_value) {
        return;
    }
    // 不选第 i 个物品
    backtrack(i + 1);
    // 选第 i 个物品
    cur_value += v[i];
    cur_weight += w[i];
    if (cur_weight == W && cur_value > max_value) {
        max_value = cur_value;
    }
    if (cur_weight < W) {
        backtrack(i + 1);
    }
    cur_value -= v[i];
    cur_weight -= w[i];
}

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