用c++完整实现装载问题的回溯算法（递归和迭代两种方式）要求有输入输出提示

在C++中，装载问题是经典的组合优化问题，如0-1背包问题，可以使用回溯算法（Backtracking）解决。这里我将展示如何用递归和迭代的方式分别实现。

**递归版本：**

#include <iostream>
using namespace std;

// 定义物品结构
struct Item {
    int weight, value;
};

bool canFit(Item* items, int n, int capacity) {
    for (int i = 0; i < n; ++i) {
        if (items[i].weight <= capacity)
            return true;
    }
    return false;
}

void backtrack(Item* items, int n, int capacity, int currWeight, bool taken[]) {
    // Base case: 如果当前重量超过容量，结束递归
    if (currWeight > capacity)
        return;

    // 打印选择的物品
    cout << "Picked item with weight: " << items[currItem].weight << ", value: " << items[currItem].value << endl;

    // 尝试不选这个物品
    taken[currItem] = false;
    if (canFit(items + 1, n - 1, capacity - items[currItem].weight))
        backtrack(items, n, capacity, currWeight, taken);

    // 尝试选这个物品
    taken[currItem] = true;
    if (currWeight + items[currItem].weight <= capacity && canFit(items + 1, n - 1, capacity))
        backtrack(items, n, capacity, currWeight + items[currItem].weight, taken);
}

int main() {
    int n, capacity;
    cout << "Enter number of items and the maximum capacity: ";
    cin >> n >> capacity;

    Item items[n];
    cout << "Enter item weights and values: ";
    for (int i = 0; i < n; ++i) {
        cin >> items[i].weight >> items[i].value;
    }

    bool taken[n] = {false};
    backtrack(items, n, capacity, 0, taken);

    return 0;
}

**迭代版本：**

由于C++标准库不支持动态规划表（DP）的原生数据结构，我们可以用栈模拟状态回溯。以下是迭代版本的实现：

#include <iostream>
#include <stack>
using namespace std;

// ...（同上，Item结构体和canFit函数）

void iterativeBacktrack(Item* items, int n, int capacity, vector<bool>& taken, stack<pair<Item*, int>>& state) {
    taken[n - 1] = false;
    state.push({items + n - 1, 0});

    while (!state.empty()) {
        pair<Item*, int> currState = state.top();
        state.pop();

        if (currState.first->weight <= capacity) {
            cout << "Picked item with weight: " << currState.first->weight << ", value: " << currState.first->value << endl;

            if (taken[currState.first - items]) continue; // 避免重复选择

            taken[currState.first - items] = true;
            if (canFit(items, n - 1, capacity - currState.first->weight)) {
                state.push({items, capacity - currState.first->weight});
            }
        } else {
            taken[currState.first - items] = false;
        }
    }
}

int main() {
    // 输入同上...
    vector<bool> taken(n, false);
    stack<pair<Item*, int>> state;
    iterativeBacktrack(items, n, capacity, taken, state);

    return 0;
}

在这个例子中，用户需要输入项目数量和最大容量，然后逐项输入重量和价值。程序会打印出所有可行的装载方案。