编辑代码

#include <iostream>
using namespace std;
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)// 输出背包内物品2
{
    if (NULL==head)
        return;
    ResultNode* curNode=head->next;
    while(curNode!=NULL)
    {
        cout<<endl<<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)// 用作销毁1
{
    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)// 按照数组中选择的路径，将该路径上的物品放入背包内0
{
    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)
// 背包最大承重，背包里最大价值，物品列表，可选物品全部个数，当前背包物品个数，当前背包重量，当前背包价值，背包，存放选择路径的数组52
{
    if(itemCount==curItemCount)// 递归出口0
	{
        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);
    // 遍历完一种结果后，用来返回上一个路口54
}
int main()
{
    Item items1[]=
	{
        Item("第一件",6,5),
        Item("第二件",5,3),
        Item("第三件",4,5),
        Item("第四件",2,3),
        Item("第五件",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 << "Max value is " << maxValue1 << endl;
    printResultList(&head1);
    return 0; 
}