用c++实现装载问题的回溯算法（递归和迭代两种方式）

装载问题，通常是指货物分配到多个容器的问题，如背包问题的一个变种。回溯算法（Backtracking）是一种用于解决这类组合优化问题的有效搜索策略，包括递归和迭代两种形式。

**递归实现：**

#include <iostream>
using namespace std;

// 容器容量，物品重量，总物品数量，已装载物品列表
int capacity, weight, items, loaded;
bool canLoad(int i) {
    return (loaded + weight[i] <= capacity);
}

void backtrack(vector<int>& items, int start) {
    if (start == items.size()) {
        // 如果所有物品都装入了，打印结果并返回
        cout << "Loaded: ";
        for (auto& item : loaded) {
            cout << item << " ";
        }
        cout << endl;
        return;
    }

    // 尝试将物品放入容器
    if (canLoad(start)) {
        loaded.push_back(items[start]);
        backtrack(items, start + 1); // 递归尝试下一个物品
    }

    // 回溯操作：如果不放，则移除当前选择并尝试其他物品
    loaded.pop_back();
    backtrack(items, start);
}

int main() {
    // 初始化数据...
    vector<int> items = {...};
    backtrack(items, 0);
    return 0;
}

**迭代实现（也称作记忆化搜索）：**

#include <vector>
#include <unordered_set>

// 状态表示当前装载的情况，使用set存储已经访问过的状态
unordered_set<vector<int>> visited;
bool canLoadIterative(vector<int>& items, int i, int loadedSoFar, int capacity) {
    if (i == items.size() && loadedSoFar <= capacity) {
        visited.insert(loadedSoFar);
        return true;
    }
    if (i >= items.size() || loadedSoFar + items[i] > capacity)
        return false;

    bool result = canLoadIterative(items, i + 1, loadedSoFar, capacity);
    if (!result && loadedSoFar + items[i] <= capacity)
        result = canLoadIterative(items, i + 1, loadedSo_far + items[i], capacity);

    if (result)
        visited.insert(loadedSoFar);
    return result;
}

int main() {
    // 初始化数据...
    vector<int> items = {...};
    if (canLoadIterative(items, 0, 0, capacity))
        // 打印装载方案...
    else
        cout << "No solution found." << endl;
    return 0;
}