编辑代码

#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);
    
}
// packWeight: 表示包能装的重量
// maxValue：当前最大价值
// items:要装包的物品
// itemCout:要装包物品的个数
// curItemCout:当前遍历过的物品个数，已经做出选择的物品的个数
// curWeight: 当前装包的物品重量
// curValue：当前装包物品的价值
// head:所有选择结果的链表
// itemSelectResult：当前的选择结果，相当于这个问题的一个解[1,1,1]表示三个物品都选了
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){
        // 满足限制条件
        // 一个解[1,1,1]
        itemSelectResult[curItemCount] = 1;
        
        //要装包的物品数量减少了1个，大问题转换成了小问题
        backpack(packWeight, maxValue, items, itemCount, curItemCount + 1, curWeight + curItem->weight, curValue + curItem->value, head, itemSelectResult);
    }

    // 遍历右子树
    // 不装它
    itemSelectResult[curItemCount] = 0;
    //要装包的物品数量减少了1个，大问题转换成了小问题
    backpack(packWeight, maxValue, items, itemCount, curItemCount+1, curWeight, curValue, head, itemSelectResult);

}

int main() {
    int packWeight = 100;
    Item items[] = {
        Item("0", 10, 20),
        Item("1", 30, 10),
        Item("2", 40, 5),
        Item("3", 50, 7),
        Item("4", 70, 9),
        Item("5", 20, 12),
        Item("6", 60, 15)
    };
    int itemCount = sizeof(items)/sizeof(Item);
    int *itemSelect = new int[itemCount]();
    ResultNode head(NULL, 0, NULL);
    int maxValue = 0;

    backpack(packWeight, maxValue, items, itemCount, 0, 0, 0, &head, itemSelect);

    cout << "Max value is " << maxValue << endl;
    printResultList(&head);

     Item items1[] = {
        Item("鸡爪", 6, 5),
        Item("鸡翅", 5, 3),
        Item("鸡腿", 4, 5),
        Item("鸡蛋", 2, 3),
        Item("鸡脖", 1, 2)
    };

    
    int *itemSelect1 = new int[3]();//记录选择方法[0,1,0]/[1,1,1]
    ResultNode head1(NULL, 0, NULL); // 记录选择的结果的
    int maxValue1 = 0; // 记选出来的最大值

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

    cout << "Max value is " << maxValue1 << endl;
    printResultList(&head1);
}