编辑代码

#include <iostream>

using namespace std;

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

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

    Item() {
        name = "";
        weight = 0;
        value = 0;
        next = NULL;
    }

    Item(Item *item) {
        name = item->name;
        weight = item->weight;
        value = item->value;
        next = item->next;
    }
};

struct Result {
    int value;
    Item *head;

    Result() {
        value = 0;
        head = new Item();
    }

    Result(Result *result) {
        value = result->value;
        head = new Item();
        head->next = result->head->next;
    }
};

Result* backpack(int packCapacity, Item *items, int itemCount)
{
    int minWeight = items[0].weight;
    for (int i = 1; i < itemCount; ++i) {
        int curWeight = items[i].weight;
        if (curWeight < minWeight) {
            minWeight = curWeight;
        }
    }

    if (packCapacity < minWeight) {
        cout << "The capacity of package "
             << packCapacity << " is less than the minimum weight of items "
             << minWeight << endl;
        return NULL;
    }

    Result** dpArray = new Result*[itemCount]();//常来记录每一行对应的数组空间

    int weightCount = packCapacity + 1;

    for (int i = 0; i < itemCount; ++i) {
        dpArray[i] = new Result[weightCount]();
    }

    // 填充表格
    for (int i = 0; i < itemCount; ++i) { 
        int curWeight = items[i].weight;
        int curValue = items[i].value;
        for (int w = minWeight; w < weightCount; ++w) { 
            int preTotalValue= 0;

            if (i > 0) {
                preTotalValue = dpArray[i - 1][w].value;
            }

            int curTotalValue = 0;

            if (w >= curWeight) {
                curTotalValue = curValue;
            }
            if ( w > curWeight && i > 0 ) {
                curTotalValue += dpArray[i-1][w - curWeight].value;
                dpArray[i][w].head->next = dpArray[i-1][w - curWeight].head->next;
            }

            int maxTotalValue = preTotalValue;

            if (maxTotalValue < curTotalValue) {
                maxTotalValue = curTotalValue;
                items[i].next = dpArray[i][w].head->next;
                dpArray[i][w].head->next = new Item(&items[i]);
            } else {
                dpArray[i][w].head->next = dpArray[i - 1][w].head->next;
            }

            // 记录下放入当前物品后，能够放w磅物品的背包能够放入物品的最大价值

            dpArray[i][w].value = maxTotalValue;

        }
    }

    //记录下最终的最大结果
    Result *result = new Result(&dpArray[itemCount - 1][weightCount - 1]);

    for (int i = 0; i < itemCount; ++i) {
        for (int j = 0; j < weightCount; ++j) {
            delete dpArray[i][j].head;
        }
        delete [] dpArray[i];
    }

    delete [] dpArray;

    return result;
}

int main()
{
    int days = 4;
    Item items[] = {
        Item("故宫", 1, 7),
        Item("颐和园", 2, 8),
        Item("长城", 3, 9),
        Item("长城", 1, 6)
    };
    int itemCount = sizeof(items)/sizeof(Item);
    Result* result = NULL;

    result = backpack(days, items, itemCount);

    if (result->value > 0) {
        cout << "Max value is " << result->value << endl;
        Item *item = result->head->next;
        Item * prev = NULL;
        cout << "Scenic spots are ";
        while ( item != NULL) {
            cout << item->name << " ";
            prev = item;
            item = item->next;
            delete prev;
        }
        cout << endl;
    }

    delete result->head;
    delete result;
}