编辑代码

#include <iostream>
using namespace std;

struct ResultNode;

struct Item {
    string name;
    int weight;
    int value;

    Item(string n, int w, int v) {
        name = n;
        weight = w;
        value = v;
    }

    Item() {
        name = "0";
        weight = 0;
    }
};

struct ResultNode
{
    Item* items;//选中的物品数组
    int itemsCount;//选中物品的数量
    ResultNode* next;//下一个可能的选择结果

    ResultNode(Item* itemsArray, int itemsArrayCount, ResultNode* nextNode) {
        items = itemsArray;
        itemsCount = itemsArrayCount;
        next = nextNode;
    }
};


void printResultList(ResultNode* head) {

    if (NULL == head) {
        return;
    }
    ResultNode* curNode = head->next;
    while (curNode != NULL)
    {
        cout << "------------------------------------" << endl;
        for (size_t i = 0; i < curNode->itemsCount; i++)
        {
            cout << curNode->items[i].name << "  重量:" << curNode->items[i].weight<<"  价值:" << curNode->items[i].value << endl;
        }
        curNode = curNode->next;
        cout << "------------------------------------" << endl;

    }
}

void deleteResultList(ResultNode* head) {
    if (NULL == head) {
        return;
    }

    ResultNode* curNode = head->next;
    while (curNode != NULL)
    {
        ResultNode* nodeToDelete = curNode;
        curNode = curNode->next;
        delete nodeToDelete;
    }

}

ResultNode* createResultNode(Item* items, int itemCount, int* itemSelectResult) {

    Item* itemsSelected = new Item[itemCount]();
    int count = 0;

    for (size_t i = 0; i < itemCount; i++)
    {
        if (itemSelectResult[i] == 1) {
            itemsSelected[count].name = items[i].name;
            itemsSelected[count].weight = items[i].weight;
            itemsSelected[count].value = items[i].value;
            ++count;
        }
    }

    return new ResultNode(itemsSelected, count, NULL);

}
//深度遍历算法
void backpack(int packWeight,
    int& maxValue,
    Item* items,
    int itemCount,
    int curItemCount,
    int curWeight,
    int curValue,
    ResultNode* head,
    int* itemSelectResult) {
    if (itemCount == curItemCount) {
    
        if (curValue > maxValue) {
            maxValue = curValue;
            deleteResultList(head);
            head->next = createResultNode(items, itemCount, itemSelectResult);
        }
        else if (curValue == maxValue) {
            ResultNode* newNode = createResultNode(items, itemCount, itemSelectResult);
            newNode->next = head->next;
            head->next = newNode;
        }
        return;
    }
    Item* curItem = &items[curItemCount];
    if (curWeight + curItem->weight <= packWeight) {
        itemSelectResult[curItemCount] = 1;
        backpack(packWeight, maxValue, items, itemCount, curItemCount + 1, curWeight + curItem->weight, curValue + curItem->value, head, itemSelectResult);
    }
    itemSelectResult[curItemCount] = 0;
    backpack(packWeight, maxValue, items, itemCount, curItemCount + 1, curWeight, curValue, head, itemSelectResult);

}

int main() {
    Item items1[] = {
       Item("物品1", 6, 5),
       Item("物品2", 5, 3),
       Item("物品3", 4, 5),
       Item("物品4", 2, 3),
       Item("物品5", 1, 2)
    };


    int* itemSelect1 = new int[5]();
    ResultNode head1(NULL, 0, NULL); 
    int maxValue1 = 0; // 记选出来的最大值

    backpack(10, maxValue1, items1, 5, 0, 0, 0, &head1, itemSelect1);

    cout << "最大价值:" << maxValue1 << endl;
    cout << "选择的物品有以下可能："<<endl;
    printResultList(&head1);
}