编辑代码

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

#define MAX_N 1000  // 最大物品数量
#define MAX_W 1000  // 最大背包容量

int n;  // 物品数量
int w[MAX_N];  // 物品重量
int v[MAX_N];  // 物品价值
int c;  // 背包容量
int maxv;  // 最大价值
int curw;  // 当前背包重量
int curv;  // 当前背包价值
int bestv[MAX_W];  // bestv[i]表示当前索引为i时，背包容量为i时的最大价值

// 计算以j为索引、背包容量为c的情况下，能够获得的最大价值
int bound(int j, int c) {
    int b = curv;
    int leftw = c - curw;
    while (j < n && leftw >= w[j]) {
        leftw -= w[j];
        b += v[j];
        j++;
    }
    if (j < n) {
        b += leftw * v[j] / w[j];
    }
    return b;
}

// 搜索第i个物品是否放入背包
void dfs(int i) {
    if (i == n) {  // 达到叶子节点，更新最大价值
        maxv = curv;
        return;
    }
    // 不选第i个物品
    bestv[i+1] = bound(i+1, c);  // 计算下一个物品的最大价值
    if (bestv[i+1] < maxv) {  // 如果最大价值都小于当前最大价值，直接返回
        return;
    }
    dfs(i+1);
    // 选第i个物品
    if (curw + w[i] <= c) {  // 可以放入背包
        curw += w[i];
        curv += v[i];
        if (curv > maxv) {  // 更新最大价值
            maxv = curv;
        }
        bestv[i+1] = bound(i+1, c);  // 计算下一个物品的最大价值
        if (bestv[i+1] > maxv) {  // 如果最大价值比当前最大价值大，继续搜索
            dfs(i+1);
        }
        curw -= w[i];  // 回溯
        curv -= v[i];
    }
}

int main() {
    printf(("请输入物品数量和背包容量："));
    // 读入数据
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        printf("请输入%d号物品的重量和价值：", i);
        scanf("%d%d", &w[i], &v[i]);
    }
    // 初始化
    maxv = curv = 0;
    curw = 0;
    bestv[0] = bound(0, c);
    // 搜索
    dfs(0);
    // 输出结果
    printf("获取物品的总价值为%d\n", maxv);
    return 0;
}