帮我用c++解决Knapsack背包问题完成一个代码按照下面要求： n个物品有重量W={w 1,…,wn}和价值P={p 1,…,pn}, 有一容量为C的背包（其中wi ,p I, CZ+）。如何选择物品装入背包，是装入物品的价值最大？ 1）编写算法，按单位重量的价值由大到小排序，重新编号。将结果打印到文件（Knapsack.txt）。 2）编写算法int InitProfit()求出初始解bestp；将结果打印到文件（Knapsack.txt）。 3）编写算法float Bound(int i)求出上界值；将结果打印到文件（Knapsack.txt）。 4）编写回溯算法void Backtrack(int t)求出最优解和最优值。将结果打印到文件（Knapsack.txt）。 5）实例：n=11, wi随机产生，范围1~20；p i随机产生，范围10~30；C等于所有物品重量和的4/5（取整数）。将结果打印到文件（Knapsack.txt）。

好的，以下是用 C++ 解决 Knapsack 背包问题的代码，分别实现了上述要求的 1~4 步骤：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>

struct Item {
    int id;
    int weight;
    int profit;
    double value;

    bool operator<(const Item& other) const {
        return value > other.value; // 按单位重量的价值由大到小排序
    }
};

int capacity; // 背包容量
std::vector<Item> items; // 物品列表

// 初始化物品列表
void InitItems(int n) {
    items.resize(n);
    std::default_random_engine rng(std::random_device{}());
    std::uniform_int_distribution<int> w_dist(1, 20);
    std::uniform_int_distribution<int> p_dist(10, 30);
    for (int i = 0; i < n; i++) {
        items[i].id = i + 1;
        items[i].weight = w_dist(rng);
        items[i].profit = p_dist(rng);
        items[i].value = static_cast<double>(items[i].profit) / items[i].weight;
    }
    std::sort(items.begin(), items.end());
}

// 打印物品列表
void PrintItems(const std::string& filename) {
    std::ofstream ofs(filename);
    ofs << "物品列表：" << std::endl;
    ofs << "编号\t重量\t价值\t单位重量价值" << std::endl;
    for (const auto& item : items) {
        ofs << item.id << "\t" << item.weight << "\t" << item.profit << "\t" << item.value << std::endl;
    }
    ofs.close();
}

// 计算初始解
int InitProfit() {
    int total_weight = 0;
    int total_profit = 0;
    for (const auto& item : items) {
        if (total_weight + item.weight > capacity) {
            break;
        }
        total_weight += item.weight;
        total_profit += item.profit;
    }
    return total_profit;
}

// 计算上界值
double Bound(int i, int w, int p) {
    if (w >= capacity) {
        return p;
    }
    double bound = p;
    int j = i + 1;
    int total_weight = w;
    while (j < items.size() && total_weight + items[j].weight <= capacity) {
        bound += items[j].profit;
        total_weight += items[j].weight;
        j++;
    }
    if (j < items.size()) {
        bound += (capacity - total_weight) * items[j].value;
    }
    return bound;
}

// 回溯搜索
void Backtrack(int t, int w, int p, int& bestp, std::vector<int>& solution) {
    if (t >= items.size() || w >= capacity) {
        if (p > bestp) {
            bestp = p;
            solution = std::vector<int>(items.size(), 0);
            for (int i = 0; i < t; i++) {
                solution[items[i].id - 1] = 1;
            }
        }
        return;
    }
    double bound = Bound(t, w, p);
    if (bound < bestp) {
        return;
    }
    Backtrack(t + 1, w, p, bestp, solution);
    Backtrack(t + 1, w + items[t].weight, p + items[t].profit, bestp, solution);
}

int main() {
    int n = 11;
    capacity = std::accumulate(items.begin(), items.end(), 0, [](int acc, const Item& item) { return acc + item.weight; }) * 4 / 5;
    InitItems(n);
    PrintItems("Knapsack.txt");

    int bestp = InitProfit();
    std::vector<int> solution(items.size(), 0);
    Backtrack(0, 0, 0, bestp, solution);

    std::ofstream ofs("Knapsack.txt", std::ios_base::app);
    ofs << "背包容量：" << capacity << std::endl;
    ofs << "初始解：" << bestp << std::endl;
    ofs << "最优解：" << bestp << std::endl;
    ofs << "最优方案：[";
    for (int i = 0; i < solution.size(); i++) {
        ofs << solution[i];
        if (i < solution.size() - 1) {
            ofs << ", ";
        }
    }
    ofs << "]" << std::endl;
    ofs.close();

    return 0;
}

其中，第 5 步骤的实例已经在代码中实现，最终输出结果保存在 Knapsack.txt 文件中。