本文共 2782 字，大约阅读时间需要 9 分钟。

建立一个二叉树，我们约定左结点表示选择装入物品，右结点表示不装入物品。假设有5个物品，物品重量是{2, 2, 6, 5, 4}，对应价值是{6, 3, 5, 4, 6}。背包的容量为10。

对于第一个物品，我们可以选择装入或者不装入。若装入，总重量为2，总价值为6。若不装入，总重量为0，总价值为0。

对于第二个物品，我们可以选择装入或者不装入。若第一个物品已经装入，则若装入第二个物品，总重量为4，总价值为9。若不装入第二个物品，总重量为2，总价值为6。若第一个物品没有装入，则若装入第二个物品，总重量为2，总价值为3。若不装入第二个物品，总重量为0，总价值为0。

依此类推，我们可以构造出这样的二叉树。通过先序遍历，即可获得背包中物品的最大总价值。

在代码实现中，我们可以使用递归的方式构建二叉树，并在遍历过程中记录最大价值。每次处理一个节点时，计算当前路径的总重量和价值。如果总重量超过背包容量，则返回空，否则继续处理左右子节点。处理完所有节点后，返回最大价值。

以下是代码示例：

#include 
   
    #include 
    
     using namespace std;typedef struct TreeNode {    long long int val;    long long int weight;    bool left;    bool right;    TreeNode *LChild;    TreeNode *RChild;    TreeNode *Parent;} TreeNode;TreeNode *init(TreeNode *node) {    node->weight = 0;    node->val = 0;    node->left = false;    node->right = false;    node->LChild = NULL;    node->RChild = NULL;    node->Parent = NULL;    return node;}TreeNode *addNode(TreeNode *parented, int w, int val) {    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));    node = init(node);    if (parented->weight + w <= c) {        node->weight = w + parented->weight;        node->val = val + parented->val;        node->Parent = parented;    } else {        node = NULL;    }    return node;}int main(int argc, char const *argv[]) {    TreeNode *head = (TreeNode *)malloc(sizeof(TreeNode));    head = init(head);    int n, c;    cin >> n >> c;    int w[1001], p[1001];    for (int i = 0; i < n; i++) {        cin >> w[i] >> p[i];    }    head = init(head);    int i = 0;    while (1) {        if (head->left && head->right && head->Parent == NULL) {            cout << "结束" << endl;            break;        }        if (head->left && head->right) {            cout << "回退" << endl;            i--;            head = head->Parent;            continue;        }        if (i >= n || head->weight >= c) {            cout << "加完数据了或者已经装满了" << endl;            if (MAX < head->val) {                MAX = head->val;            }            head->left = true;            head->right = true;            continue;        }        if (!head->left) {            cout << "加左结点 i = " << i << endl;            head->left = true;            head->LChild = addNode(head, w[i], p[i]);            if (head->LChild != NULL) {                i++;                head = head->LChild;            }        } else if (!head->right) {            cout << "加右结点 i = " << i << endl;            head->right = true;            head->RChild = addNode(head, 0, 0);            if (head->RChild != NULL) {                i++;                head = head->RChild;            }        }    }    cout << MAX << endl;}
    
   

通过先序遍历，我们可以找到背包中物品的最大总价值。代码中使用了递归的方式构建二叉树，并在遍历过程中记录最大价值。每次处理一个节点时，计算当前路径的总重量和价值。如果总重量超过背包容量，则返回空，否则继续处理左右子节点。处理完所有节点后，返回最大价值。

在实际应用中，可以根据需要调整递归深度和性能优化措施，确保程序能够高效运行。

转载地址：http://xjccz.baihongyu.com/