本文共 2864 字，大约阅读时间需要 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/