编辑代码

#include <iostream>

using namespace std;

struct Item {
    string name;
    int day;
    int score;
    Item *next;

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

    Item() {
        name = "";
        day = 0;
        score = 0;
        next = NULL;
    }

    Item(Item *item) {
        name = item->name;
        day = item->day;
        score = item->score;
        next = item->next;
    }
};

struct Result {
    int score;
    Item *head;

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

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

Result* backpack(int packCapacity, Item *items, int itemCount) {
    
    int minday = items[0].day;

    // 找出最小天数，进行健壮性检查
    for (int i = 1; i < itemCount; ++i)
    {
        int curday = items[i].day;
        if (curday < minday) {
            minday = curday;
        }
    }

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


    //创建表格，横轴是景点，纵轴是期限内景点的时间
     Result** dpArray = new Result*[itemCount]();//常来记录每一行对应的数组空间

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

    // 填充表格
    for (int i = 0; i < itemCount; ++i)
    {
        // 记录景点的时间和评分
        int curday = items[i].day;
        int curscore = items[i].score;
        for (int w = minday; w < dayCount; ++w)
        {
            // 记录不去当前景点的情况下，景点能够达到的最大评分
            int preTotalscore= 0;

            if (i > 0) {
                preTotalscore = dpArray[i - 1][w].score;
            }
            
            // 记录去当前景点的情况下，去的景点能够达到的最大评分
            int curTotalscore = 0;

            // 如果当前景点能够去，记录下景点的评分
            if (w >= curday) {
                curTotalscore = curscore;
            }
            // 如果记录当前景点后时间还有剩余，且确实还有其它景点，加上剩余的时间能够加入景点的最大评分
            if ( w > curday && i > 0 ) {
                curTotalscore += dpArray[i-1][w - curday].score;
                dpArray[i][w].head->next = dpArray[i-1][w - curday].head->next;
            }
      
            // 找出加入当前景点和不加入当前景点情况下，加入的景点能够达到的最大评分
            int maxTotalscore = preTotalscore;

            if (maxTotalscore < curTotalscore) {
                maxTotalscore = curTotalscore;
                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].score = maxTotalscore;

        }    
    }

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

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

    delete [] dpArray;
    
    return result;
}

int main() {
    int packCapacity = 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(packCapacity, items, itemCount);

    if (result->score > 0) {
        cout << "最大价值是：" << result->score << endl;
        Item *item = result->head->next;
        Item * prev = NULL;
        cout << "能获得最大价值的景点有：";
        while ( item != NULL) {
            cout << item->name << ", ";
            prev = item;
            item = item->next;
            delete prev;
        }
        cout << endl;
    }

    delete result->head;
    delete result;    
}