01背包回溯问题c++

### 关于C++实现01背包问题的回溯算法

#### 代码示例与解释

以下是使用C++编写的针对01背包问题的回溯算法示例：

#pragma once
#include <iostream>
#include <vector>

using namespace std;

// 定义全局变量存储物品重量和价值以及最大承重
int maxWeight;
vector<int> weights, values;

// 存储当前路径的价值总和和最佳解的最大价值
int current_value = 0, best_value = 0;

void backtrack(int i, int weight_sum) {
    if (weight_sum > maxWeight || i >= weights.size()) { // 边界条件判断
        return;
    }
    
    if (i == weights.size() - 1 && weight_sum + weights[i] <= maxWeight) { // 到达叶子节点并满足约束条件
        if (current_value + values[i] > best_value) {
            best_value = current_value + values[i];
        }
    } else if (i < weights.size() - 1) { // 非叶子节点处理逻辑
        // 不选第i个物品的情况
        backtrack(i + 1, weight_sum);
        
        // 选择第i个物品的情况下继续探索
        if (weight_sum + weights[i] <= maxWeight) {
            current_value += values[i]; // 更新当前累计价值
            
            backtrack(i + 1, weight_sum + weights[i]);
            
            current_value -= values[i]; // 回退操作恢复状态
        }
    }
}

/// 主函数调用入口
void solveKnapsack(const vector<int>& w, const vector<int>& v, int W) {
    weights = w;
    values = v;
    maxWeight = W;
    backtrack(0, 0); // 开始从第一个物品考虑起
    
    cout << "The maximum value that can be put in a knapsack of capacity "
         << maxWeight << " is " << best_value << endl;
}

此段程序通过递归方式遍历所有可能的选择组合来寻找最优解。当遇到不满足约束条件的情形时提前终止分支，从而减少不必要的计算开销[^1]。

对于每一个决策点而言，存在两种可能性——要么选取该位置上的物体加入到已装载集合中；要么放弃它而转向考察下一个候选对象。上述方法即基于这种思路构建而成，在每一步都尝试做出局部最优抉择以期最终获得整体上最好的结果[^2]。